Here is some Pari/GP (Version 2.9.4) code calculating the 64 largest primes less than 2^127, a 39-digit number. The largest such prime is 2^127-1 (a Mersenne prime), then 2^127-25, 2^127-39, and so on. We print the offsets from 2^127.
? count=0 ; for(i=1 , +oo , x=2^127-i ; if(isprime(x) , print(i) ; count+=1 ; if(count==64 , break)))
1 25 39 295 309 507 511 577 697 735 801 957 1081 1105 1141 1201 1231 1447 1485 1495 1741 1747 2197 2437 2509 2569 2589 2601 2607 2619 2665 2721 2829 2839 2901 3045 3195 3255 3331 3381 3415 3489 3787 3801 3805 3811 3927 3931 3949 3961 4299 4441 4557 4705 4789 4897 4971 5017 5115 5127 5197 5235 5277 5299
time = 355 ms.
We limit our attention for the rest of this post to primes which have 2 has a primitive root, i.e., 2 is a generator of the multiplicative group. These primes are useful for iterating the recurrence x = 2*x mod p. Here are the 64 largest primes less than 2^127 which have 2 as a primitive root.
? count=0 ; for(i=1 , +oo , x=2^127-i ; if(isprime(x) , if(2==znprimroot(x) , print(i) ; count+=1 ; if(count==64 , break))))
309 507 957 1141 1485 1741 2437 2509 2589 2619 2829 2901 3045 3195 3331 3381 3805 3811 3931 3949 4299 4557 4789 4971 5115 5235 5277 5299 5325 5389 5395 5475 5989 5997 6115 6157 6555 7725 7899 8179 8347 8541 8637 8757 9147 9405 9525 10165 10755 10819 11325 12291 12397 12411 12549 12765 13341 13357 13555 13597 14421 16411 16491 16765
time = 3,310 ms.
Note that znprimroot returns the smallest primitive root, which is why we can use it to compactly test whether 2 is a primitive root. This is a convenient hack, not necessarily computationally efficient, because znprimroot then searches forward for a number that is a primitive root if 2 is not one, while we don't care as soon as it isn't 2. Previously, the (possibly) right way to do this. Both our hack and the previous way factor p-1, which Pari/GP does quickly for 127-bit numbers but which probably dominates running time.
2^127-5115 and 2^127-51115 (the latter is beyond the search range listed above) have particularly memorable forms.
Next, we limit to safe primes, primes p such that (p-1)/2 is also prime:
? count=0 ; for(i=1 , +oo , x=2^127-i ; if(isprime(x) , if(isprime((x-1)/2) , if(2==znprimroot(x) , print(i) ; count+=1 ; if(count==64 , break)))))
2901 25149 37245 53781 76845 87069 91509 92061 135621 265101 277869 293829 334941 373869 386421 402429 422061 431829 435165 461109 462549 507021 577101 601821 623325 644949 646749 706221 725205 751485 754845 779421 784629 919245 967365 994749 1265229 1271781 1319349 1327149 1348725 1352109 1369941 1429461 1478061 1491549 1501701 1508301 1629045 1630629 1638669 1653501 1682541 1714965 1738869 1746429 1817205 1841301 1847565 1867845 1897965 1966965 1997685 2048709
time = 2min, 11,015 ms.
Let's compute the discrete logarithm of 3 modulo the safe prime 2^127-2901. Safe primes are particularly difficult moduli for computing discrete logarithms. This takes about 3 minutes and requires 128 MB memory.
? allocatemem
*** Warning: new stack size = 16000000 (15.259 Mbytes).
? allocatemem
*** Warning: new stack size = 32000000 (30.518 Mbytes).
? allocatemem
*** Warning: new stack size = 64000000 (61.035 Mbytes).
? allocatemem
*** Warning: new stack size = 128000000 (122.070 Mbytes).
? m=2^127-2901
170141183460469231731687303715884102827
? p=znprimroot(m)
time = 1 ms.
Mod(2, 170141183460469231731687303715884102827)
? q=znlog(3,p)
time = 2min, 38,368 ms.
1260226675522897863468033786677990456
? p^q
Mod(3, 170141183460469231731687303715884102827)
Incidentally, although computing one discrete log takes about 3 minutes, computing N discrete logs with the same modulus could be done in less than N times the time, for sufficiently large N. This is the LOGJAM attack which first does some precomputation on the modulus. We do not explore it any further here.
A type of prime that is the opposite of safe primes are primes p whose factorization of p-1 is smooth. We abbreviate "largest factor of p-1" to LFP-1. First we search for records of LFP-1 smoothness. The offset from 2^127 is the first number on each output line, and the largest prime factor is the second number.
? best=2^128 ; for(i=1 , 500000 , x=2^127-i ; if(isprime(x) , if(2==znprimroot(x) , f=factor(x-1) ; li=f[matsize(f)[1],1] ; if(li<best , best=li ; print(i," ",li)))))
309 74294021089185055945745438733353
507 256083780808648884634349
1141 905121482977
12765 82796310769
30331 430177817
242059 152631881
444651 4717717
time = 2min, 11,158 ms.
Next, a list of all primes between 2^127 and 2^127-10^7 with primitive root 2 and LFP-1 less than 5 million.
? for(i=1 , 10^7 , x=2^127-i ; if(isprime(x) , if(2==znprimroot(x) , f=factor(x-1) ; li=f[matsize(f)[1] , 1] ; if(li<5000000 , print(i , " " , li)))))
444651 4717717
1152555 4644209
6693891 1035043
time = 45min, 35,892 ms.
We decrease the LFP-1 threshold to 1 million and do a parallel search of offsets up to 1250 million (1.25e9).
? parfor(big=0 , 1249 , my(chunk=1000000) ; print("# " , big*chunk) ; for(i=big*chunk , ((1+big)*chunk)-1 , my(x=2^127-i) ; if(isprime(x) , if(2==znprimroot(x) , my(f=factor(x-1)) ; my(li=f[matsize(f)[1] , 1]) ; if(li<10^6 , print("found " , i , " " , li))))))
61934019 733351
82938397 144961
133436701 541001
157468965 922549
242770389 241603
289644739 501031
326962747 439961
366131749 807997
367704027 716399
432311541 338609
446813139 807463
463930957 293863
513949771 831967
612950469 932563
623586765 433369
635285307 515639
708623581 969113
736096155 805789
744318579 472937
771767739 916477
816240435 593629
886559845 944453
925511355 944773
1042014051 755627
1075625227 313399
1088549797 380753
1187590339 920021
1190065141 869471
1240244611 206369
The prime with smoothest LFP-1 in the range was 2^127-82938397 .
? m=2^127-82938397;
? print(factor(m-1))
time = 1 ms.
[2, 1; 3, 1; 5, 1; 83, 1; 233, 1; 257, 1; 337, 1; 467, 1; 4481, 1; 8101, 1; 8369, 1; 9187, 1; 17921, 1; 144961, 1]
? p=znprimroot(m)
time = 1 ms.
Mod(2, 170141183460469231731687303715801167331)
Pari/GP can compute discrete logs for this modulus very quickly. We compute 10000 discrete logs to estimate the average time.
? d=82938397 ; m=2^127-d ; p=znprimroot(m) ; s=0 ; for(i=10001 , 20000 , s+=znlog(i,p)) ; s
time = 17,481 ms.
850318960248652201518304123860924430097815
1.75 milliseconds per discrete log, or about 90000 times faster than discrete logarithm modulo a safe prime.
We can precompute the order of the multiplicative group. The order is p-1 as expected.
? p=znprimroot(2^127-82938397)
Mod(2, 170141183460469231731687303715801167331)
? znorder(p)
170141183460469231731687303715801167330
time = 2 ms.
If we precompute the order and pass it to znlog as its optional third argument, discrete logs with this modulus take 1.17 milliseconds per discrete log, or 130,000 faster than with the safe prime modulus:
? p=znprimroot(2^127-82938397) ; o=znorder(p) ; s=0 ; for(i=10001 , 20000 , s+=znlog(i,p,o)) ; s
time = 11,718 ms.
850318960248652201518304123860924430097815
If we precompute the factorization of the order, we speed up to 1.12 milliseconds per discrete log, or 140,000 times faster than with the modulus a safe prime.
? o1=znorder(p) ; o2=[o1,factor(o1)]
[170141183460469231731687303715801167330, [2, 1; 3, 1; 5, 1; 83, 1; 233, 1; 257, 1; 337, 1; 467, 1; 4481, 1; 8101, 1; 8369, 1; 9187, 1; 17921, 1; 144961, 1]]
? s=0 ; for(i=10001 , 20000 , s+=znlog(i,p,o2)) ; s
time = 11,153 ms.
850318960248652201518304123860924430097815
However, we discovered these znorder tricks too late, so they won't be used further.
We continue to focus on this modulus 2^127-82938397. We compute the discrete logs of odd numbers less than 20 million, giving records (measured in bits) seeking the smallest discrete log result.
? best=2^128 ; for(i=3 , 20*10^6 , if(i%2 , q=znlog(i,p) ; if(q<best , best=q ; print(i," ",log(q)/log(2)))))
3 126.60861957417140874567308610111676924
5 125.84204150578944850225376775754144592
7 125.54487559498150016959290161376213647
11 121.61876667227321730143768163344664841
57 119.26302102454656004110219710283194089
117 118.33868727548874546101027476382298987
293 117.41240586378025000861705496132624191
1047 115.98190253251845806763291780031659908
19651 113.82915853125528889576941297788981983
36273 112.02758003583497136349282231453930018
43847 111.75932967140139743211725892707714229
111013 109.88911848702144118712865772303140653
418639 108.56088710127544789965180319861891917
1187883 107.83680647635499874285392261408464158
1568169 105.46972571057206839981959364031149651
15948733 104.77044754456292177721188142035714805
18053633 102.43314618087649638970890791286463580
time = 4h, 54min, 34,045 ms.
1.77 milliseconds per discrete log.
Next we do a parallel search up to 500 million, filtering for answers less than 2^103:
? my(chunk=1000000) ; my(m=2^127-82938397) ; my(p=znprimroot(m)) ; parfor(big=1 , 500 , print("# ",big*chunk) ; for(i=big*chunk , ((1+big)*chunk)-1 , if(i%2 , my(q=znlog(i,p)) ; if(q<2^103 , print("found ",i," ",log(q)/log(2))))))
Results sorted by size:
found 82938397 6.9886846867721658532800038923017027697
found 171848755 98.009237044095953515097095663026711413
found 341768329 99.246033026596466741135988164496297146
found 220519863 99.502082521428754440701200103415444437
found 79244343 100.02039742477967334114350603030590954
found 365274687 101.09069522081284726933747163714490844
found 210553081 101.18394853067516178942704803045412011
found 91501943 101.23292263789306627626659032965908669
found 51740489 101.73859976085589548746612838921350273
found 395905149 102.41160267007178229191681729083127290
found 18053633 102.43314618087649638970890791286463580
found 189820555 102.65604910446208699071098797773121492
found 26937603 102.65891491097708177429669650928303269
found 130319341 102.70632408678270701825939285407339555
found 474335751 102.90247484952858397973538375832421765
found 383886557 102.90614848684696682752146489213589054
found 19201299 102.99981173599943664391050799371599292
The smallest found, size 6.99 bits, was a pathological case:
? znlog(82938397 , znprimroot(2^127-82938397))
127
Or equivalently
2^127 = 82938397 (mod 2^127-8293837)
Note that small powers of 82938397 also have small discrete logs:
? znlog(82938397^2 , znprimroot(2^127-82938397))
254
This is simply from squaring both sides of the earlier equation:
2^(127*2) = (2^127)^2 = 82938397^2 (mod 2^127-8293839)
The smallest non-pathological answer found, size 98.0 bits, was the discrete log of 171848755:
? znlog(171848755 , znprimroot(2^127-82938397))
318948234431409899300209908475
Or equivalently
2^318948234431409899300209908475 = 171848755 (mod 2^127-8293839)
Compare the size in digits of that discrete log answer to that of the discrete log of 3, an answer of typical magnitude:
? znlog(3 , znprimroot(2^127-82938397))
129715597792854129200088529850276735523
Incidentally, smoothness of LFP-1 is not the only thing that determines Pari/GP's speed of computing discrete log. To demonstrate this, we experiment with a prime with an even smoother LFP-1. We search for the largest prime with primitive root 2, less than 2^127, of the form (1 + 2^a * 3^b * 5^c):
? best=0 ; forvec(x=[ [1,127] , [0,floor(127*log(2)/log(3))] , [0,floor(127*log(2)/log(5))] ] , p=1+2^x[1]*3^x[2]*5^x[3] ; if(p>best , if((p<2^127) && isprime(p) && (2==znprimroot(p)) , best=p ; print(x))))
[1, 0, 0]
[1, 0, 1]
[1, 0, 13]
[1, 4, 24]
[1, 4, 34]
[1, 14, 39]
[1, 38, 28]
time = 402 ms.
The largest such prime is 1 + 2 * 3^38 * 5^28 .
? p=1+2*3^38*5^28
100646295970156199410557746887207031251
? isprime(p)
1
? znprimroot(p)
Mod(2, 100646295970156199410557746887207031251)
This is a 127-bit prime number, but its value is 40% smaller than 2^127-82938397 with which we were working with earlier:
? p=1+2*3^38*5^28
100646295970156199410557746887207031251
? p/2.^127
0.59154576172053286462083796835459363959
? p=2^127-82938397
170141183460469231731687303715801167331
? p/2.^127
0.99999999999999999999999999999951253191
We compute 10000 discrete logs as we did before, first without precomputation of the order, second, with it, and third with the factorization of the order:
? p=znprimroot(1+2*3^38*5^28) ; s=0 ; for(i=10001 , 20000 , s+=znlog(i,p)) ; s
time = 24,921 ms.
502005227028798759415955242763719138488151
? p=znprimroot(1+2*3^38*5^28) ; o=znorder(p) ; s=0 ; for(i=10001 , 20000 , s+=znlog(i,p,o)) ; s
time = 20,181 ms.
502005227028798759415955242763719138488151
? o1=znorder(p) ; o2=[o1,factor(o1)] ; s=0 ; for(i=10001 , 20000 , s+=znlog(i,p,o2)) ; s
time = 20,135 ms.
502005227028798759415955242763719138488151
Despite the modulus being smaller and LFP-1 being smoother, discrete log computations take 2.5 milliseconds, 2.0 milliseconds, and 2.0 milliseconds respectively, slower than 2^127-82938397 (1.75 ms, 1.17 ms, 1.12 ms). I don't know the internals of how Pari/GP computes discrete logs to be able to explain why this modulus is slower.
No comments :
Post a Comment