We search for safe primes of the form base^e-offset, finding records of primes for which the size of its offset is small relative to the size of base^e. Here is some Pari/GP code:
base=10 ; best=1 ; for(e=2 , +oo , j=base^e ; imax=floor(base^(e*best)) ; for(i=1 , imax , p=j-i ; if(p%12==11 && ispseudoprime(p) && ispseudoprime((p-1)/2) , r=log(i)/log(base)/e ; if(r<best , print("found " , base , " ^ " , e , " - " , i , " " , r) ; best=r ) ; break)) ; if(best<0.02 , print("exit bits " , e*log(base)/log(2)) ; break))
(We ignore the safe prime 7, which is the only safe prime not equal to 11 mod 12.)
The code could easily be modified to search for other types of primes or numbers, for example, primes which have base as a primitive root. (Note that square numbers are never primitive roots, and 3 is among the numbers which are never primitive roots of safe primes.)
Below is sample output for base=2:
found 2 ^ 4 - 5 0.58048202372184058696757985737234754397
found 2 ^ 6 - 5 0.38698801581456039131171990491489836264
found 2 ^ 9 - 9 0.35221388904914581810083087643284811306
found 2 ^ 10 - 5 0.23219280948873623478703194294893901759
found 2 ^ 18 - 17 0.22708126895835218934744811171168913078
found 2 ^ 21 - 9 0.15094880959249106490035608989979204845
found 2 ^ 33 - 9 0.096058333377039768572953875390776758107
found 2 ^ 87 - 129 0.080588819027853495636067592924320505066
found 2 ^ 90 - 41 0.059528355606867596590733014528032318897
found 2 ^ 134 - 197 0.056880983727286390050625384097285838999
found 2 ^ 157 - 333 0.053371836732937975444364853920438270811
found 2 ^ 162 - 317 0.051286043395922267002167977218548339280
found 2 ^ 186 - 677 0.050553828083736541670346093145941923838
found 2 ^ 210 - 65 0.028677941966802164325081581351171832902
found 2 ^ 298 - 341 0.028233650768537491493307002167454185846
found 2 ^ 340 - 293 0.024102226042418376101558516098013625491
found 2 ^ 349 - 285 0.023366241000149295195179306006716450164
found 2 ^ 560 - 6389 0.022573882900525915510686751422096638374
found 2 ^ 622 - 2537 0.018181523800745882954488020212862493026
exit bits 622.00000000000000000000000000000000000
time = 6,292 ms.
As an example, we explain the final safe prime found, 2^622-2537. The size of the offset, 2537, is log(2537)/log(2) = 11.3 bits. The size of 2^622 is 622 bits. The ratio of sizes 11.3/622 = 0.01818 is the value in the last column. We exit when we find a safe prime whose offset is less than 2% of the size of the number. "exit bits" means we were examining numbers of size 622 bits when the loop exited.
We conjecture that if the exit criterion were removed, the code will print out an infinite sequence of safe primes; that is, the ratio can become arbitrarily small, for any base.
We also conjecture that there is an approximate relation between "exit bits" and the exit threshold (e.g., 0.02) that is independent of the base.
The variable imax allows skipping exponents which don't have a nearby safe prime. For a given exponent, we only need to search while the offset (i) is small enough, smaller than the minimum ratio (best) found so far. If we exceed the ratio, we can move on to the next exponent.
Here is sample output for base 10.
found 10 ^ 2 - 17 0.61522446068913696427008494716416851500
found 10 ^ 3 - 17 0.41014964045942464284672329810944567667
found 10 ^ 6 - 41 0.26879730945328924908490197499469679992
found 10 ^ 11 - 353 0.23161588230798386959064266508805101799
found 10 ^ 12 - 41 0.13439865472664462454245098749734839996
found 10 ^ 18 - 137 0.11870669817535593158682925706193276298
found 10 ^ 29 - 701 0.098128207516091677829793873698286358679
found 10 ^ 39 - 6077 0.097017672726854266549531476387573940085
found 10 ^ 43 - 4373 0.084669290170810627903606008656545850941
found 10 ^ 49 - 1961 0.067193420278934368213090673085028286544
found 10 ^ 50 - 2093 0.066415384566773729575729970575723083480
found 10 ^ 51 - 2321 0.065993630205017994231995256885704115554
found 10 ^ 52 - 1217 0.059332511119808942093586653920665154322
found 10 ^ 56 - 1433 0.056361539114238294214190949899218660294
found 10 ^ 63 - 953 0.047287188899021054103697457900274798012
found 10 ^ 78 - 1637 0.041205752300153095377856711500679927390
found 10 ^ 95 - 3041 0.036663330738359285910081017233299693981
found 10 ^ 106 - 2753 0.032451001994276700528394385467803919102
found 10 ^ 144 - 2417 0.023494976738942016442647307029558583499
found 10 ^ 164 - 6233 0.023138397115195113465786325043453474505
found 10 ^ 183 - 12161 0.022322236549043647104445774474408957967
found 10 ^ 194 - 19277 0.022087832202920203458993772557365736358
found 10 ^ 200 - 22601 0.021770638276461319119867503235712184052
found 10 ^ 207 - 30461 0.021660599790474218559518306497749615433
found 10 ^ 231 - 43073 0.020061494030646520996064784295927605952
found 10 ^ 238 - 40241 0.019347347750084787263082024329913973700
exit bits 790.61888658319223879313602421847486186
time = 23,815 ms.
Not sure what all this is useful for. Usually when we want a safe prime, we have a fixed exponent in mind (to achieve a certain level of cryptographic security) and don't care too much about the size of the offset.
No comments :
Post a Comment