Re: index calculus vs pollard rho

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

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
28 -> 30
29 -> 31
30 -> 36
31 -> 36
32 -> 50
33 -> 50
34 -> 52
35 -> 60
36 -> 65
37 -> 66
38 -> 70
39 -> 70
40 -> 75
41 -> 75
42 -> 86
43 -> 90
44 -> 90
45 -> 95
46 ->100
47 ->105
48 ->105
49 ->115
50 ->115 

Cheers,
Bill.

? znbench()
[27,29]:4:4
[27,37]:0:16
[28,31]:0:4
[29,31]:8:8
[29,39]:4:16
[30,36]:12:12
[30,40]:4:20
[31,35]:4:12
[32,35]:64:12
[32,42]:28:20
[32,52]:24:72
[33,37]:48:16
[33,43]:44:24
[33,53]:16:72
[34,39]:28:20
[34,44]:56:28
[34,54]:72:80
[35,38]:24:16
[35,45]:125:28
[35,55]:12:96
[35,65]:28:296
[36,38]:300:16
[36,46]:289:36
[36,56]:128:104
[36,66]:276:309
[37,42]:228:20
[37,47]:96:40
[37,57]:228:112
[37,67]:112:357
[38,43]:544:28
[38,48]:160:40
[38,58]:413:124
[38,68]:264:409
[38,78]:292:1052
[39,43]:160:24
[39,49]:461:52
[39,59]:240:132
[39,69]:340:433
[39,79]:332:1152
[40,42]:593:20
[40,50]:384:52
[40,60]:889:152
[40,70]:369:464
[40,80]:845:1236
[41,45]:241:32
[41,51]:636:64
[41,61]:885:164
[41,71]:849:505
[41,81]:392:1373
[42,46]:1196:40
[42,52]:873:72
[42,62]:756:201
[42,72]:2917:568
[42,82]:985:1509
[42,92]:1260:3853
[43,48]:1204:44
[43,53]:1192:76
[43,63]:1016:217
[43,73]:3000:636
[43,83]:3124:1649
[43,93]:4012:4380
[44,49]:1321:52
[44,54]:80:88
[44,64]:3741:252
[44,74]:1681:692
[44,84]:2160:1813
[44,94]:2513:4688
[45,50]:2761:60
[45,55]:1168:97
[45,65]:5252:296
[45,75]:4749:793
[45,85]:1416:2104
[45,95]:2437:5312
[46,48]:761:48
[46,56]:7188:108
[46,66]:10357:321
[46,76]:7392:797
[46,86]:6480:2233
[46,96]:5957:5568
[46,106]:3749:13950
[47,50]:5280:56
[47,57]:312:117
[47,67]:10665:349
[47,77]:1945:888
[47,87]:6809:2373
[47,97]:3772:6221
[47,107]:12898:15373
[48,52]:5745:72
[48,58]:3372:120
[48,68]:14530:352
[48,78]:8117:1020
[48,88]:6168:2629
[48,98]:9650:6800
[48,108]:7337:17934
[49,54]:13725:97
[49,59]:18629:140
[49,69]:18606:440
[49,79]:25403:1084
[49,89]:8585:2929
[49,99]:6905:7593
[49,109]:10962:20517
[49,119]:17646:49540
[50,53]:9881:85
[50,60]:14041:168
[50,70]:6893:464
[50,80]:34086:1333
[50,90]:32966:3129
[50,100]:25030:7945
[50,110]:11137:20197
[50,120]:32042:53451