Re: index calculus vs pollard rho

[Karim Belabas <Karim.Belabas@math.u-bordeaux.fr>]

* 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

These two models yield the following thresholds:
? for(P = 27, 50, printf("%d -> %3d\n",P, floor(a*P+b)))
27 ->  26
28 ->  29
29 ->  33
30 ->  37
31 ->  41
32 ->  45
33 ->  49
34 ->  53
35 ->  57
36 ->  60
37 ->  64
38 ->  68
39 ->  72
40 ->  76
41 ->  80
42 ->  84
43 ->  88
44 ->  92
45 ->  95
46 ->  99
47 -> 103
48 -> 107
49 -> 111
50 -> 115

? for(P = 27, 50, printf("%d -> %3d\n",P, floor(A*P^2+B)))
27 ->  30
28 ->  33
29 ->  36
30 ->  39
31 ->  42
32 ->  45
33 ->  48
34 ->  51
35 ->  55
36 ->  58
37 ->  62
38 ->  66
39 ->  70
40 ->  74
41 ->  78
42 ->  82
43 ->  86
44 ->  91
45 ->  95
46 -> 100
47 -> 104
48 -> 109
49 -> 114
50 -> 119

Presumably, the second one will scale better :-)

Cheers,

    K.B.
--
Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
Universite Bordeaux 1          Fax: (+33) (0)5 40 00 69 50
351, cours de la Liberation    http://www.math.u-bordeaux1.fr/~kbelabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux1.fr/  [PARI/GP]
`