motivated by the discrete logarithm problem, here are the largest safe primes less than doubly exponential decimal powers of 2 that have 2 as a generator, investigating a range over which the discrete logarithm problem is difficult (512-4096 bits). note that to compute 2^2^decimal, we need to have enough floating-point precision, e.g., 1200 decimal digits around 2^2^11.9 .
future post: a better idea, namely 2^round(2^decimal)-offset , which does not require lots of floating-point precision.
2^2^9 = 2^512
2^2^9 - 38117
round(2^2^9.1) - 72619
round(2^2^9.2) - 170121
round(2^2^9.3) - 1827601
round(2^2^9.4) - 129653
round(2^2^9.5) - 26399
round(2^2^9.6) - 1131742
round(2^2^9.7) - 1388849
round(2^2^9.8) - 1035881
round(2^2^9.9) - 639207
2^2^10 - 1503509
round(2^2^10.1) - 1911383
round(2^2^10.2) - 2577837
round(2^2^10.3) - 1994567
round(2^2^10.4) - 2275208
round(2^2^10.5) - 3020521
round(2^2^10.6) - 791606
round(2^2^10.7) - 4781949
round(2^2^10.8) - 4258632
round(2^2^10.9) - 2309609
2^2^11 - 4801589
round(2^2^11.1) - 14215609
round(2^2^11.2) - 445254
round(2^2^11.3) - 5197046
round(2^2^11.4) - 4196131
round(2^2^11.5) - 14421559
round(2^2^11.6) - 22291245
round(2^2^11.7) - 6437075
round(2^2^11.8) - 43514517
round(2^2^11.9) - 876641
2^2^12 - 13463237
2^2^12 = 2^4096
Pari/GP code:
\p1250
realprecision = 1252 significant digits (1250 digits displayed)
gettime(); for(j=90, +oo, i=j/10; x=round(20+2^i*log(2)/log(10)); default(realprecision, x); start=round(2^2^i); for(k=0, +oo, y=start-k; if(y%12==11 && ispseudoprime(y) && ispseudoprime((y-1)/2) && 2==znprimroot(y), print(j, " ", k, " ", gettime); break)))
about 16 hours of computation to do 9.0 to 12, most of it spent between 11.0 and 12.0 .
solving 2^x = 3 modulo these safe primes are an ordered set of discrete logarithm challenges. target could be different from 3. current record for integer discrete logarithm is 795 bits, or 2^2^9.63 .
here is a parallel Pari/GP code to search for safe primes. we print in the sequential block to avoid overlapping output. (the sequential block is a useful feature.) we search in decreasing size so that the hardest exponents can get the longest amount of time.
parfor(j=0, 30, my(x=(120-j)/10); my(start=round(2^2^x)); my(answer); for(i=0, start, my(p=start-i); if(p%12==11 && ispseudoprime(p) && ispseudoprime((p-1)/2) && 2==znprimroot(p), return([x,i]))), r, printf("%.1f %d", r[1], r[2]))
although parallelization in Pari/GP is nice, it is in general not a good tool for this kind of search because ispseudoprime does very little initial trial division or sieving to eliminate composites with small factors. future post: searching for safe primes below 2^round(2^decimal) with a sieve.
previously, safe primes below even larger (integer) powers of 2, not limiting to generator 2.
here are some decimal powers of 10:
10^2 = 100
10^2.1 = 126
10^2.2 = 158
10^2.3 = 200
10^2.4 = 251
10^2.5 = 316
10^2.6 = 398
10^2.7 = 501
10^2.8 = 631
10^2.9 = 794
10^3 = 1000
10^3.1 = 1259
(previously on decimal powers of 10.)
the largest safe primes, with generator 2, less than doubly exponential decimal powers of 10:
10^10^2 - 166517
round(10^10^2.1) - 108280
round(10^10^2.2) - 161302
round(10^10^2.3) - 18978
round(10^10^2.4) - 3993695
round(10^10^2.5) - 2044685
round(10^10^2.6) - 4718163
round(10^10^2.7) - 848382
round(10^10^2.8) - 6852251
round(10^10^2.9) - 20784122
10^10^3 - 3159413
round(10^10^3.1) - 8357832
these numbers compare with powers of 2 as follows:
10^10^2 = googol = 10^100 = 2^332
10^10^3 = 10^1000 = 2^3322
10^10^3.1 = 10^1259 = 2^4182
here is some parallel Pari/GP code to search for a safe prime corresponding to just one exponent (3.1). although global variables are forbidden inside parfor, the curly braces create a local scope within which we can create a "my" variable shared among threads.
{ my(start=round(10^10^3.1)) ; parfor(i=0, +oo, my(p=start-i) ; p%12==11 && ispseudoprime(p) && ispseudoprime((p-1)/2) && 2==znprimroot(p), r, if(r, return(i))) }
No comments :
Post a Comment