Karim Belabas on Mon, 03 Oct 2005 20:31:04 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
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]