Karim BELABAS on Wed, 13 Oct 1999 19:29:02 +0200 (MET DST) |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: polynomials over GF(p) |
> 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/