Bill Daly on Fri, 23 Jan 2009 16:43:18 +0100


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: Polmod factorization


Denis Simon wrote:
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]
`

    

  
Thanks. This is exactly what I was looking for.

Regards, Bill