## Saturday, December 04, 2021

### [qlcpuedj] safe primes below many powers of 2

we give the largest safe prime below selected powers of 2.  we also give additional safe primes below them until one which has 2 as a primitive root (generator).  the exponents are rounded decimal powers of 2 (so the sequence is doubly exponential)  (previously, not rounding until the end which requires a large amount of floating point precision.)

this work expands on previous work and OEIS A181356.

also previously, safe primes below powers of 10.

for example, in the list below, 2^3.1 ~= 8.57, and round(2^3.1) = 9, so 2^round(2^3.1) = 2^9 = 512.  the largest safe primes less than 512 are 2^9-9 = 512-9 = 503 (which has least primitive root 5), 2^9-33 = 512-33 = 479 (which has least primitive root 13), and 2^9-45 = 512-45 = 467 (which has least primitive root 2), where we stop, having found a safe prime with primitive root 2.  the offsets are -9, -33, and -45.

future post (srzrbviv): source code and implementation discussion.

currently, the recommendation for cryptographic security for Diffie-Hellman key exchange when using the integer discrete logarithm problem is safe prime moduli of size at least 2^11 = 2048 bits.

2^round(2^1.4) = 2^3 : -1 -3
2^round(2^1.5) = 2^3 : -1 -3
2^round(2^1.6) = 2^3 : -1 -3
2^round(2^1.7) = 2^3 : -1 -3
2^round(2^1.8) = 2^3 : -1 -3
2^round(2^1.9) = 2^4 : -5
2^round(2^2.0) = 2^4 : -5
2^round(2^2.1) = 2^4 : -5
2^round(2^2.2) = 2^5 : -9 -21
2^round(2^2.3) = 2^5 : -9 -21
2^round(2^2.4) = 2^5 : -9 -21
2^round(2^2.5) = 2^6 : -5
2^round(2^2.6) = 2^6 : -5
2^round(2^2.7) = 2^6 : -5
2^round(2^2.8) = 2^7 : -21
2^round(2^2.9) = 2^7 : -21
2^round(2^3.0) = 2^8 : -29
2^round(2^3.1) = 2^9 : -9 -33 -45
2^round(2^3.2) = 2^9 : -9 -33 -45
2^round(2^3.3) = 2^10 : -5
2^round(2^3.4) = 2^11 : -9 -21
2^round(2^3.5) = 2^11 : -9 -21
2^round(2^3.6) = 2^12 : -17 -89 -149
2^round(2^3.7) = 2^13 : -45
2^round(2^3.8) = 2^14 : -161 -197
2^round(2^3.9) = 2^15 : -165
2^round(2^4.0) = 2^16 : -269
2^round(2^4.1) = 2^17 : -285
2^round(2^4.2) = 2^18 : -17 -1265 -1661
2^round(2^4.3) = 2^20 : -233 -449 -989
2^round(2^4.4) = 2^21 : -9 -285
2^round(2^4.5) = 2^23 : -321 -729 -1101
2^round(2^4.6) = 2^24 : -317
2^round(2^4.7) = 2^26 : -677
2^round(2^4.8) = 2^28 : -437
2^round(2^4.9) = 2^30 : -1385 -1697 -2645
2^round(2^5.0) = 2^32 : -209 -1409 -3509
2^round(2^5.1) = 2^34 : -641 -1001 -1637
2^round(2^5.2) = 2^37 : -45
2^round(2^5.3) = 2^39 : -381
2^round(2^5.4) = 2^42 : -2201 -3737 -5417 -12581
2^round(2^5.5) = 2^45 : -573
2^round(2^5.6) = 2^49 : -2709
2^round(2^5.7) = 2^52 : -473 -2729 -2933
2^round(2^5.8) = 2^56 : -2249 -2837
2^round(2^5.9) = 2^60 : -3677
2^round(2^6.0) = 2^64 : -1469
2^round(2^6.1) = 2^69 : -165
2^round(2^6.2) = 2^74 : -545 -9521 -22745 -23777 -26045
2^round(2^6.3) = 2^79 : -2001 -2709
2^round(2^6.4) = 2^84 : -5297 -7013
2^round(2^6.5) = 2^91 : -81 -5661
2^round(2^6.6) = 2^97 : -6909
2^round(2^6.7) = 2^104 : -15773
2^round(2^6.8) = 2^111 : -429
2^round(2^6.9) = 2^119 : -3981
2^round(2^7.0) = 2^128 : -15449 -21509
2^round(2^7.1) = 2^137 : -849 -1785 -2289 -30189
2^round(2^7.2) = 2^147 : -2601 -15201 -30249 -38145 -44841 -49761 -92565
2^round(2^7.3) = 2^158 : -665 -14117
2^round(2^7.4) = 2^169 : -20493
2^round(2^7.5) = 2^181 : -20265 -83793 -96093
2^round(2^7.6) = 2^194 : -6641 -37961 -38057 -42257 -74681 -86801 -139565
2^round(2^7.7) = 2^208 : -4973
2^round(2^7.8) = 2^223 : -28929 -44901
2^round(2^7.9) = 2^239 : -87429
2^round(2^8.0) = 2^256 : -36113 -188069
2^round(2^8.1) = 2^274 : -54605
2^round(2^8.2) = 2^294 : -184181
2^round(2^8.3) = 2^315 : -51321 -61245
2^round(2^8.4) = 2^338 : -35861
2^round(2^8.5) = 2^362 : -169805
2^round(2^8.6) = 2^388 : -17297 -156377 -222113 -365369 -375737 -497693
2^round(2^8.7) = 2^416 : -222749
2^round(2^8.8) = 2^446 : -324857 -835781
2^round(2^8.9) = 2^478 : -699821
2^round(2^9.0) = 2^512 : -38117
2^round(2^9.1) = 2^549 : -1005069
2^round(2^9.2) = 2^588 : -313793 -406997
2^round(2^9.3) = 2^630 : -104585 -636521 -813917
2^round(2^9.4) = 2^676 : -322229
2^round(2^9.5) = 2^724 : -52517
2^round(2^9.6) = 2^776 : -356033 -1710317
2^round(2^9.7) = 2^832 : -1281293
2^round(2^9.8) = 2^891 : -1926369 -2217081 -4672149
2^round(2^9.9) = 2^955 : -1077885
2^round(2^10.0) = 2^1024 : -1093337 -1370753 -1428353 -1503509
2^round(2^10.1) = 2^1097 : -3161265 -3560373
2^round(2^10.2) = 2^1176 : -2056193 -2069357
2^round(2^10.3) = 2^1261 : -2634393 -4262745 -4668993 -4944945 -5565909
2^round(2^10.4) = 2^1351 : -25905 -1138665 -3569025 -3720261
2^round(2^10.5) = 2^1448 : -549269
2^round(2^10.6) = 2^1552 : -551729 -6104357
2^round(2^10.7) = 2^1663 : -611625 -774609 -1455849 -1719765
2^round(2^10.8) = 2^1783 : -1233705 -3645345 -4163709
2^round(2^10.9) = 2^1911 : -3231309
2^round(2^11.0) = 2^2048 : -1942289 -4801589
2^round(2^11.1) = 2^2195 : -3502989
2^round(2^11.2) = 2^2353 : -1678485
2^round(2^11.3) = 2^2521 : -4968453
2^round(2^11.4) = 2^2702 : -246797
2^round(2^11.5) = 2^2896 : -761717
2^round(2^11.6) = 2^3104 : -4210193 -8338889 -10214933
2^round(2^11.7) = 2^3327 : -775149
2^round(2^11.8) = 2^3566 : -16802105 -37290401 -56582861
2^round(2^11.9) = 2^3822 : -9543617 -11776781
2^round(2^12.0) = 2^4096 : -10895177 -13463237
2^round(2^12.1) = 2^4390 : -77336201 -79007045
2^round(2^12.2) = 2^4705 : -24442605
2^round(2^12.3) = 2^5043 : -1559505 -12588225 -40350225 -44478165
2^round(2^12.4) = 2^5405 : -81935433 -86932389
2^round(2^12.5) = 2^5793 : -11998425 -33851673 -36961425 -50712993 -83738889 -236665449 -254515869
2^round(2^12.6) = 2^6208 : -20057957
2^round(2^12.7) = 2^6654 : -11162645
2^round(2^12.8) = 2^7132 : -7052309
2^round(2^12.9) = 2^7643 : -44120649 -123495021
2^round(2^13.0) = 2^8192 : -43644929 -49930517
2^round(2^13.1) = 2^8780 : -22581833 -25207709
2^round(2^13.2) = 2^9410 : -10428521 -103539077
2^round(2^13.3) = 2^10086 : -29814917
2^round(2^13.4) = 2^10809 : -6562329 -216052833 -262814913 -415344465 -429846909
2^round(2^13.5) = 2^11585 : -370812549
2^round(2^13.6) = 2^12417 : -103708449 -294381693
2^round(2^13.7) = 2^13308 : -10956077
2^round(2^13.8) = 2^14263 : -397079661
2^round(2^13.9) = 2^15287 : -214216065 -312159765
2^round(2^14.0) = 2^16384 : -364486013
2^round(2^14.1) = 2^17560 : -141642533
2^round(2^14.2) = 2^18820 : -339964313 -571288529 -898757417 -1027256537 -1156399229
2^round(2^14.3) = 2^20171 : -276625749
2^round(2^14.4) = 2^21619 : -674266449 -833225181
2^round(2^14.5) = 2^23170 : -259994441 -366289061
2^round(2^14.6) = 2^24834 : -415810805
2^round(2^14.7) = 2^26616 : -2909149877
2^round(2^14.8) = 2^28526 : -520866521 -811123361 -990961337 -1485278921 -1487483597
2^round(2^14.9) = 2^30574 : -568083185 -1447030925
2^round(2^15.0) = 2^32768 : -718982153 -2543122349
2^round(2^15.1) = 2^35120 : -881530949
2^round(2^15.2) = 2^37641 : -454965045
2^round(2^15.3) = 2^40342 : -132843485