Searching for strong primes

[Niels Möller]

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
  24cf5f83655d23dca3ad961c62f356208552bb9ed529077096966d670c354e4abc9804f1
  746c08ca18217c32905e462e36ce3be39e772c180e86039b2783a2ec07a28fb5c55df06f
  4c52c9de2bcbf6955817183995497cea956ae515d2261898fa051015728e5a8aaac42dad
  33170d04507a33a85521abdf1cba64ecfb850458dbef0a8aea71575d060c7db3970f85a6
  e1e4c7abf5ae8cdb0933d71e8c94e04a25619dcee3d2261ad2ee6bf12ffa06d98a0864d8
  7602733ec86a64521f2b18177b200cbbe117577a615d6c770988c0bad946e208e24fa074
  e5ab3143db5bfce0fd108e4b82d120a92108011a723c12a787e6d788719a10bdba5b2699
  c327186af4e23c1a946834b6150bda2583e9ca2ad44ce8dbbbc2db04de8ef92e8efc141f
  becaa6287c59474e6bc05d99b2964fa090c3a2233ba186515be7ed1f612970cee2d7afb8
  1bdd762170481cd0069127d5b05aa993b4ea988d8fddc186ffb7dc90a6c08f4df435c934
  02849236c3fab4d27c7026c1d4dcb2602646dec9751e763dba37bdf8ff9406ad9e530ee5
  db382f413001aeb06a53ed9027d831179727b0865a8918da3edbebcf9b14ed44ce6cbace
  d4bb1bdb7f1447e6cc254b332051512bd7af426fb8f401378cd2bf5983ca01c64b92ecf0
  32ea15d1721d03f482d7ce6e74fef6d55e702f46980c82b5a84031900b1c9e59e7c97fbe
  c7e8f323a97a7e36cc88be0f1d45b7ff585ac54bd407b22b4154aacc8f6d7ebf48e1d814
  cc5ed20f8037e0a79715eef29be32806a1d58bb7c5da76f550aa3d8a1fbff0eb19ccb1a3
  13d55cda56c9ec2ef29632387fe8d76e3c0468043e8f663f4860ee12bf2d5b0b7474d6e6
  94f91e6dbe115974a3926f12fee5e438777cb6a932df8cd8bec4d073b931ba3bc832b68d
  9dd300741fa7bf8afc47ed2576f6936ba424663aab639c5ae4f5683423b4742bf1c97823
  8f16cbe39d652de3fdb8befc848ad922222e04a4037c0713eb57a81a23f0c73473fc646c
  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.