Re: idealstar

[Bill Allombert <Bill.Allombert@math.u-bordeaux1.fr>]

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.