Re: index calculus vs pollard rho

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

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.

Cheers,
Bill.