Bill Allombert on Tue, 09 Dec 2008 11:59:10 +0100 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: idealstar |
On Sun, Dec 07, 2008 at 07:00:53PM +0100, Karim Belabas wrote: > * Bill Allombert [2008-12-03 04:48]: > > On Tue, Dec 02, 2008 at 06:33:17PM +0100, Karim Belabas wrote: > > > I'd have a look at "ideallog" ... > > > > > > As you mentionned, the bottleneck is the computation of discrete logs in > > > (Z_K / P) for maximal ideals P dividing I. This will be slow if Norm P - 1 > > > is not smooth ( basic Pohlig-Hellman + Shanks ). > > > > Well, a basic index calculus implementation for znlog would beat > > the current znlog, use less memory and be easy to implement > > (as long as we do not implement sieving/Lanczos/etc.). > > > > Is it worth the trouble ? > > I think so. It's a reasonably basic number theoretic algorithm that > would benefit a lot of PARI functions (in a range where they are > currently not usually applied, granted). > > I would gratefully include a reasonable implementation. I am working on a generic implementation of Pollard rho discrete log currently. I have a quickly written GP script that implement index calculus over (Z/nZ)* (with single large prime variation, but no sieving at all), this perform roughly like Shanks but in O(x^(1/3)) in time and space, for moderate size input. I am afraid we would need to implement some sparse matrix algebra, at least structured Gaussian reduction, to get reasonnable performance. Cheers, Bill.