The Landau algorithm can handle the cases in GF(p) s.t. p doesn't divide deg(G). I didn't mention this, because I wasn't interested in deg(G)>p, as I'm only interested in permutation polys over GF(p), which have deg(F)<p. The other cases (called "non-tame") are handled by a companion paper to the one I referenced by Prof./Dr. von zur Gathen. I've been using Maxima (an open source version of Macsyma); I don't believe that its polydecomp routine uses the Landau algorithm -- at least I haven't been able to get it to properly handle finite field cases. I have submitted a bug report; we'll see what comes back. I'm pretty sure Maple implements some of the best poly decomp algorithms, as von zur Gathen is Canadian, as is Maple. Mathematica might implement a good one, perhaps. I implemented a version of the Landau algorithm for my own use in Maxima. My version is quick & very dirty; I merely wanted to see what it was doing & whether it worked. At 06:26 PM 4/3/2016, Warren D Smith wrote:
I suppose you could call a poly "prime" if it has no such decomposition. (And I use the term literally: "de-composition.") New kind of primeness notion.
Seems to me Macsyma et al ought to offer finding this decomposition as yet another capability. Could be useful. If Landau does it over finite fields then doing it over integers (and perhaps rationals?) could be done via some kind of chinese remaindering of finite field results.
In a finite field, there is a problem however. Some polynomial decomposition F(x)=G(H(x)) could happen, even though H and/or G actually have greater degree than F. Right?
Can Landau detect those? Doubt it.
-- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)