Skip to content(if available)orjump to list(if available)

Sophie Germain Prime Project

Sophie Germain Prime Project

1 comments

·June 7, 2025
Visit

throwaway81523

That is silly, generating them takes a bit of searching but not THAT much. The trick is to generate random odd numbers n, then do some fast trial divisions to check whether n and 2n+1 might both be prime. Usually those tests will fail fast (one or both are composite). Otherwise do pseudoprime tests. The events "n is prime" and "2n+1 is prime" are close to independent so basically use the prime number theorem, Pr[both prime] = approx 1/ln(n)^2. So for 4096 bits, that's around 1 in 10 million. You can chuck out vast swaths very quickly so you might have to do a few tens of thousands of pseudoprime checks, of which a modern midrange x86 box can do maybe 1000/sec. So you should be able to generate a 4096 bit pair in under a minute without fancy implementation methods.

That C program is kind of nuts and unnecessary. Since most of the computation time will be in the mpz library, you might as well use a simpler wrapper written in Python or whatever. If you want to go really fast, maybe you can parallelize the trial divisions with SIMD or a GPU.

Also, for cryptography, nobody cares about these primes any more. They use elliptic curves now.