4
$\begingroup$

What's the industry standard for an efficient finding large Sophie Germain primes?

As a part of request handling in my application, I need to generate Paillier key.

My current approach is to generate a pseudorandom probably prime number q backed up by Miller-Rabin test, then setting p = 2q + 1 and checking if p is also prime with Miller-Rabin and Baillie-PSW. This is repeated until p is prime.

loop {
  q <- randomPrime(nbits - 1) // generates probably prime number, 
                              // performs Miller-Rabin tests on the result
  p = 2q + 1
  return if isPrime(p)  //applying the Miller-Rabin & Baillie-PSW tests 
}

For nbits = 1024 one loop step takes about 100ms on my laptop. Not that bad, but in order to find desired p and q I need to execute several loop steps. The best result so far was 156 retries (~16s), the worst one was 1616 retries (~160s).

It's a way above required latency so I wonder what's considered the correct approach nowadays.

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ See math.stackexchange.com/questions/870626/… for a short cut which uses only a base-2 Fermat test for the second number. And there is a similar question by @fgrieu at mathoverflow.net/questions/295516/… $\endgroup$ Commented Jun 26, 2018 at 16:01
  • 1
    $\begingroup$ So it's enough to check 2^{p-1} ≡ 1 (mod n) instead of running expensive isPrime(p) ? $\endgroup$ Commented Jun 26, 2018 at 21:20
  • $\begingroup$ Yes, if you know that $(p-1)/2$ is prime, then $2^{p-1} \equiv 1 \pmod p$ implies that $p$ is prime as well. On the other hand, that observation doesn't save you that much time (essentially, a few MR iterations at the very end when you do find a prime $p$) $\endgroup$ Commented Jun 26, 2018 at 21:57

1 Answer 1

Reset to default
3
$\begingroup$

I don't know of any industry standards, however it's obvious that your code is fairly suboptimal.

The initial randomPrime() will effectively pick a candidate number $q$, and then spend a lot of time ensuring that number is prime. Now, half the time it'll pick a $q \equiv 1 \pmod 3$; if so, p will be a multiple of 3, and so you've just wasted all that time testing if $q$ is prime.

Now, what all random prime routines I've seen do is first ensure that their candidate number doesn't have any small factors (so we don't need to run our expensive primality tests on those values); this can be done either by computing $q \bmod s$ for small primes $s$, or by creating a sieve (a bitmap where each bit $i$ corresponds a value $a + bi$; the bit gets marked if $a + bi$ has a small factor).

Both methods can be extended to check either $q$ or $p = 2q+1$ has a small factor:

  • For the explicit $q \bmod s$ computation, we skip it if that is either 0 or $(s-1)/2$

  • For the sieve case, we mark bits where $a + bi \bmod s$ is either 0 or $(s-1)/2$

Doing this will significantly reduce the number of iterations you'll need to perform.

Now, if your randomPrime() logic is in a library you can't touch, this advice doesn't help you. However, if you can do it, this will be of help.

Improve this answer
$\endgroup$
3
  • $\begingroup$ That's a very good suggestion. I dig into randomPrime and isPrime implementation and found it's already doing an optimization you mentioned. That is, checks mod for 15 small primes before running expensive tests. I wonder if it's possible to select q in some special way to increase the possibility it's a Sophie Germain prime but did not find anything about it. $\endgroup$ Commented Jun 26, 2018 at 21:17
  • 1
    $\begingroup$ Two things: 1) you could do better than checking the first 15 small primes. If performing a $q \bmod s$ for single precision $s$ is 1000 times faster than a Miller-Rabin iteration (and it should be considerably faster than that), then it's a win to test all primes $< 1000$. Doing sieving is an even bigger when (as it makes sense to remove more small primes), but it's more work to implement 2) if you could modify the randomPrime code, you could insert the test I suggested directly (which would ensure that $p$ doesn't have tiny factors either) $\endgroup$ Commented Jun 26, 2018 at 21:50
  • $\begingroup$ These comments should move into the answer. Also, see this answer $\endgroup$ Commented Jan 24, 2020 at 17:10

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.