Karim Belabas on Fri, 23 Jan 2009 10:01:07 +0100

 Re: Polmod factorization

* 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]

`