Re: nfeltreducemodpr changed?

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

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/