Re: index calculus vs pollard rho

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

On Sat, May 10, 2014 at 08:40:51PM +0200, Bill Allombert wrote:
> On Thu, Apr 10, 2014 at 01:12:27AM +0200, Karim Belabas wrote:
> > * Bill Allombert [2014-04-09 23:43]:
> > > On Thu, Apr 03, 2014 at 05:28:24PM +0200, Bill Allombert wrote:
> > > > 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.
> > > 
> > > I join some benchmarks:
> > > [27,29]:4:8 means we are computing in (Z/lZ)* with l of 29 bits in a subgroup of
> > > order p of 27 bit. The number after the first colon is the time for
> > > Shanks/Pollard rho and the second for the linear sieve.
> > > (Remember that Pollard rho has probabilistic running time).
> > > 
> > > The thresholds are about:
> > > p -> l
> > > 27 -> 29
> > [...]
> > > 50 ->115 
> > 
> > A simple linear regression on your threshold data yields
> > 
> >   log_2(l) ~ a * log_2(p) + b
> > 
> > for a = 3.88, b = -78.78  (max. error ~ 5.55). Switching to a linear sieve when
> >   log_2(p) >= 27
> > and
> >   log_2(l) <= a * log_2(p) + b
> > will recover something close to your thresholds.
> > 
> > In fact, assuming your linear sieve implementation follow the theoretical
> > model, the threshold should rather be determined by something resembling
> >   sqrt(p) ~ exp(C*(log l log log l)^(1/2))
> > that would yield
> >   log(p) ~ 2C * (log l log log l)^(1/2)
> > 
> > A linear regression between (log_2(p))^2 and log_2(l) yields
> >   log_2(l) ~ A (log_2(p))^2 + B
> > for A = 0.05, B = -6
>  
> I have created a branch 'bill-Fp_easylog' which implement this threshold.
> Please give feedback.

Well, I have pushed a fix for this issue using Karim formula:

   23- faster znlog when p-1 has only smallish prime factors.

Please check for any slowdown.

Cheers,
Bill.