# Searching for strong primes

Niels Möller nisse at lysator.liu.se
Thu Mar 13 22:24:56 UTC 2014

```After a discussion on the ietf-ssh list, I tried to write a little
program to regenerate the primes in
https://www.rfc-editor.org/rfc/rfc3526.txt. E.g,

p = 2^8192 - 2^8128 + 2^64 * { floor(2^8062 pi) + 4743157 } + 2^64-1

where the number 4743157 is supposed to be the smallest non-negative
number such that both p and (p-1)/2 are prime. Available at

http://www.lysator.liu.se/~nisse/misc/next-strong-prime.c

The tricks used are probably familiar on this list. I think the main
novelty is that I start by doing a little bit of benchmarking to
determine a suitable limit for the trial division. One should use primes
up to a limit B, where B is roughly the ratio of the time for one modexp
to the time for trial divison by one additional prime. Which can be
pretty large.

On shell the program completed in a bit less than an hour, using a limit
of around 47 000 000:

Using 2814866 primes for sieving, largest p = 47715229
[...]
p = 0xffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc7402
0bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d
51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae
9f24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361c55d39a69163fa8fd
746c08ca18217c32905e462e36ce3be39e772c180e86039b2783a2ec07a28fb5c55df06f
33170d04507a33a85521abdf1cba64ecfb850458dbef0a8aea71575d060c7db3970f85a6
e5ab3143db5bfce0fd108e4b82d120a92108011a723c12a787e6d788719a10bdba5b2699
becaa6287c59474e6bc05d99b2964fa090c3a2233ba186515be7ed1f612970cee2d7afb8
1bdd762170481cd0069127d5b05aa993b4ea988d8fddc186ffb7dc90a6c08f4df435c934
db382f413001aeb06a53ed9027d831179727b0865a8918da3edbebcf9b14ed44ce6cbace
d4bb1bdb7f1447e6cc254b332051512bd7af426fb8f401378cd2bf5983ca01c64b92ecf0
32ea15d1721d03f482d7ce6e74fef6d55e702f46980c82b5a84031900b1c9e59e7c97fbe
c7e8f323a97a7e36cc88be0f1d45b7ff585ac54bd407b22b4154aacc8f6d7ebf48e1d814
cc5ed20f8037e0a79715eef29be32806a1d58bb7c5da76f550aa3d8a1fbff0eb19ccb1a3
13d55cda56c9ec2ef29632387fe8d76e3c0468043e8f663f4860ee12bf2d5b0b7474d6e6
94f91e6dbe115974a3926f12fee5e438777cb6a932df8cd8bec4d073b931ba3bc832b68d
9dd300741fa7bf8afc47ed2576f6936ba424663aab639c5ae4f5683423b4742bf1c97823
ea306b4bcbc8862f8385ddfa9d4b7fa2c087e879683303ed5bdd3a062b3cf5b3a278a66d
2a13f83f44f82ddf310ee074ab6a364597e899a0255dc164f31cc50846851df9ab48195d
ed7ea1b1d510bd7ee74d73faf36bc31ecfa268359046f4eb879f924009438b481c6cd788
9a002ed5ee382bc9190da6fc026e479558e4475677e9aa9e3050e2765694dfc81f56e880
b96e7160c980dd98edd3dfffffffffffffffff
k = 4743157
elapsed time 3404.86s

The bound is perhaps not optimal; I haven't saved all results but I
think it was a bit faster with the smaller bound 10 000 000 (perhaps the
benchmarking misses cache effects when the prime table gets large).

/Niels

--
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.

```