Karim Belabas on Mon, 03 Oct 2005 20:31:04 +0200

 Re: taking polynomials modulo integer

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

```