Karim BELABAS on Fri, 12 Feb 1999 17:38:24 +0100 (MET)

[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: Discrete logarithm for small numbers

[Ismael Jimenez Calvo:]
> 	I miss a function for the discrete logarith in Z_p in the pari
> package. I propose and include in this mail --as attachement-- a
> function of complexity O( \sqrt p log( \sqrt p ) ) which can find in some
> seconds a discrete logarithm in a group of order of about a million.
> Somebody knows a faster function usefull in groups of moderate size?
> Thank you very much,

The ideallog function (over Q = nfinit(x)) does exactly that, but is not
suited for "big" primes (10^6 should still be ok though).

I'm including a simple-minded function znlog (limited to prime modulus,
say, less than 10^12) in version 2.0.14.alpha, which I hope to release on


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/