Re: polynomials over GF(p)

[Karim BELABAS <Karim.Belabas@math.u-psud.fr>]

> Does anyone know how to multiply polynomials in GF(p) (Especially when
> p=2)?

Depends on what you're looking for.

Under GP or in "lazy" library programming, just define coefficients to be of
type t_INTMOD (e.g P *= Mod(1,p) under GP if P belongs to Q[X], and work with
the resulting P).

If you want efficient computations, use polynomials in Z[x] and reduce the
coefficients mod p once in a while.

If you want really efficient computations, which is the case if I understand
your last comment correctly, you'll need to work in library mode with single
precision integers and adapt polynomial multiplication (+ Karatsuba [we have
no FFT yet]) for that case. It's not exactly trivial, but it's doable [I
would say about 15 minutes work for me to produce a quick and dirty hack, but
I wrote the original code]. Depending on the degrees involved, it might be a
good idea to add an FFT multiplication for these polynomials ...

A comprehensive solution may be included by default in release 2.2 when (and
if) a new type is introduced for single precision integers [it already exists
for testing purposes (type t_SMALL, undocumented), but most interesting
functions don't understand it, and it's not yet a valid leaf for most
recursive objects].

Good luck,

  Karim.

P.S: A completely different solution would be to use Bruno Haible's CLN
package (which features rather efficient polynomial arithmetic, including
FFT), or LiDIA + CLN if you'd prefer an interpreter to C++ programming.

[see: http://www.informatik.th-darmstadt.de/TI/LiDIA/]
__
Karim Belabas                    email: Karim.Belabas@math.u-psud.fr
Dep. de Mathematiques, Bat. 425
Universite Paris-Sud             Tel: (00 33) 1 69 15 57 48
F-91405 Orsay (France)           Fax: (00 33) 1 69 15 60 19
--
PARI/GP Home Page: http://hasse.mathematik.tu-muenchen.de/ntsw/pari/