Finding primes

In cryptography, we often need to find large prime numbers. One way to do this is to pick random numbers that are the right size until you find one that's a prime. This might take a while when we're working with numbers that are as big as the ones that we typically use in cryptography. How long will this take?

One way to answer that question is by using the prime number theorem. Let the function π(x) be the number of primes less than or equal to x. The prime number theorem says that limx→∞π(x) / (x / log x) = 1, or that x / log x is a good approximation to π(x) for large values of x.

Here's how well π(x) (black) and x / log x (red) agree:

Image001

An even better approximation to π(x) is x / (log x + 1). Here's how well π(x) (black) and x / (log x + 1) (green) agree:

Image002

But since for numbers of the sizes that we often use in cryptography log x and log x + 1 are fairly close, so we can use the easier approximation without worrying too much.

One consequence of the prime number theorem is that the probability of a number n being prime is roughly 1 / log n. Here's what log n looks like for numbers that are the sizes of those that we often use in cryptography:

n

log n

2512

354.891

21,024

709.783

21,536

1064.67

So suppose that we want to generate two random 512-bit primes, like we might need to create a 1,024-bit RSA modulus. The chances of a randomly-chosen 512-bit integer being prime is about 1 in 355, so that we'd expect to find a prime in about 355/2, or about 177 attempts.

This obviously isn't the best strategy: half of randomly-chosen integers will be even, so we don't want to waste time considering them. If we look at only odd integers, this will reduce the expected number of trials by 1/2, or down to about 89 attempts. We could even continue this strategy for other small primes. One-third of randomly-chosen integers are multiples of 3, for example, so we might not want to consider multiples of 3, etc. But for the simple strategy of just trying random odd 512-bit integers, we should expect to find a 512-bit prime in about 89 tries.

Leave a Reply

Your email address will not be published. Required fields are marked *