Re: taking polynomials modulo integer

["Karim Belabas" <belabas@math.u-bordeaux1.fr>]

* bil@beeb.net [2005-10-03 19:34]:
> Hi,
> I've not had much experience using gp as yet, but think it's very good.
> I now have a problem for which I haven't been able to figure out the
> right magic words...
> I have a polynomial and wish to square it and take the result modulo
> an integer. For example:
> 
> 	f = x + x^3 + x^7 + x^11
> 
> 	Mod(f^2, 13)
> 
> gives an error message:
> 
>   ***   forbidden division t_POL % t_INT.
> 
> I need something that will use Fermat's Little Theorem to reduce
> the powers to be within the range of the modulus, 
> i.e. (x^11)^2 = x^22 == x^10 (mod 13) { using == for congruence symbol}
> 
> Can anyone point me at the right function to apply?

Assuming operations are restricted to addition and multiplication, you can
replace f by

  F = Mod(f * Mod(1,13), x^13 - x)

( view it as an element of (Z/13Z)[x] / (x^13 - x) ). After all
computations, you may apply lift() [repeatedly] to the result.

A completely different approach is to compute f(a), for all a in Z/13Z,
compute with those values, then use polinterpolate().

Hope this helps,

    Karim.
-- 
Karim Belabas                  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-bordeaux.fr/~belabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux.fr/  [PARI/GP]