Karim BELABAS on Sun, 4 Aug 2002 14:55:05 +0200 (MEST) |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: nfeltreducemodpr changed? |
On 18 Jul 2002, John Jones wrote: > Comparing versions 2.1.1 and 2.2.3, I see that the output format of > nfeltreducemodpr has changed from > > [Mod(4, 7), Mod(5, 7), Mod(0, 7), Mod(1, 7), Mod(0, 7), Mod(0, 7), Mod(0, 7)]~ > > to > > x^3 + 5*x + 4 > > I don't see any mention of this in the CHANGES file, nor a change in > its documentation. Ooops, my mistake. This is a major side effect of 2.2.3-Changed-20: 20- rewrote most *modpr functions The old modpr routines were very inefficient since they computed in characteristic 0 [using the number field multiplication table], then reduced the result modulo a prime ideal. E.g., for a prime of degree 1 above 2, we computed using huge matrices (with possibly huge rational coefficients), instead of F_2. Now, nfmodprinit picks a generating polynomial T for F_{p^f} ( = F_p[X]/(T) ) over F_p, and initializes data to efficiently project O_{K, \wp} --> F_{p^f} and lift F_{p^f} --> O_K. Internally, all computations are done in F_{p^f}, which is a major boost for bnr* routines (discrete log computations) and relative basis algorithms (a la ROUND 2). I kept the old nfeltxxxmodpr routines for compatibility reasons [they are not used anywhere in library code nowadays], but since they are trivial wrappers to the new nfreducemodpr code, they return an element in F_{p^f} (viewed as (Z/pZ)[X] / (T) ). I will make sure they give the same output as before. Thanks for spotting this, Karim. P.S: it remains to document all modular routines (to work in finite fields and various quotients of polynomial rings), and possibly devise an interface for (efficient/less cumbersome) GP programming with finite fields [ unfortunately, ffinit() already exists, and definitely doesn't return a "finite field" structure. Sigh... ] -- Karim Belabas Tel: (+33) (0)1 69 15 57 48 Dép. de Mathematiques, Bat. 425 Fax: (+33) (0)1 69 15 60 19 Université Paris-Sud Email: Karim.Belabas@math.u-psud.fr F-91405 Orsay (France) http://www.math.u-psud.fr/~belabas/ -- PARI/GP Home Page: http://www.parigp-home.de/