Re: Polmod factorization

[Denis Simon <Denis.Simon@math.unicaen.fr>]

Dear Bill,

You are probably also interested in the function factornf
(see also nffactor).
Be careful of the choice of the variables !
For example : 

gp > f=polcyclo(5)
%1 = x^4 + x^3 + x^2 + x + 1
gp > fy=subst(f,x,y);
gp > factornf(f,fy)
%3 = 
[x + Mod(-y, y^4 + y^3 + y^2 + y + 1) 1]

[x + Mod(-y^2, y^4 + y^3 + y^2 + y + 1) 1]

[x + Mod(-y^3, y^4 + y^3 + y^2 + y + 1) 1]

[x + Mod(y^3 + y^2 + y + 1, y^4 + y^3 + y^2 + y + 1) 1]

Denis SIMON.

On Fri, 23 Jan 2009, Karim Belabas wrote:

> * Bill Daly [2009-01-23 07:10]:
> > If f(x) is an irreducible polynomial in x, then Mod(x,f(x)) is a generic 
> > root of f(x), and the algebra mod f(x) is isomorphic (I think) to the 
> > algebra of the field generated by appending any root of f(x) to Q. Is there 
> > a way of factoring f(x) mod f(x)? What I have in mind is that for some 
> > polynomials where Mod(x,f(x)) is a root, then there may be other rational 
> > functions of x which are also roots of f(x), e.g. if f(x) is polcyclo(n), 
> > then Mod(x^a,f(x)) is a root whenever a is coprime to n. I don't however 
> > see any easy way of finding such roots with polmods in PARI. What, if 
> > anything, am I overlooking?
> 
> For general polmods, nothing. On the other hand the formulation suggests that
> you're actually considering the special case f \in Q[X]. Then you may just use
> nfgaloisconj(f), which settles the case of Mod(x,f):
> 
> (09:45) gp > f = polcyclo(5); v = nfgaloisconj(f)
> %1 = [x, x^2, -x^3 - x^2 - x - 1, x^3]~
> 
> \\ the ordering is a bit strange in this case; roots are sorted according to
> \\ the lexicographic order on Q^deg(f)
> 
> This settles the case of Mod(x, f); if you're interested in the conjugates of 
> more general Mod(a(x), f), use subst:
> 
> (09:45) gp > a = x^2 + x; vector(#v, i, lift( subst(a, x, Mod(v[i],f)) ))
> %2 = [x^2 + x, -x^3 - x - 1, -x^2 - x - 1, x^3 + x]
> 
> \\ lift() introduced for readability ...
> 
> Analogous ideas are also implemented over a finite field.
> 
> Cheers,
> 
>     K.B.
> --
> Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
> Universite Bordeaux 1          Fax: (+33) (0)5 40 00 69 50
> 351, cours de la Liberation    http://www.math.u-bordeaux1.fr/~belabas/
> F-33405 Talence (France)       http://pari.math.u-bordeaux1.fr/  [PARI/GP]
> `
>