Denis Simon on Fri, 23 Jan 2009 10:20:23 +0100

 Re: Polmod factorization

Dear Bill,

You are probably also interested in the function factornf
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]
>
>

`