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