Bill Allombert on Sat, 10 May 2014 20:40:57 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: index calculus vs pollard rho |
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.