Re: index calculus vs pollard rho

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

On Thu, Apr 03, 2014 at 03:22:02PM +0200, Pascal Molin wrote:
> The following znlog uses index calculus on a 46 bits subgroup, but p itself
> is large,
> this is slow (and memory-demanding)
> 
> *gp* > p=nextprime(2^120); znlog(Mod(3,p),Mod(2,p),p-1)
> 
> time = 51,617 ms.
> 
> %21 = 391862826185609110238504885400229618
> 
> while the same is easier to compute with pollard

The issue is that the threshold for Pohlig-Hellman algorithm is set to 27 bits
independently of the size of p.

Cheers,
Bill.