If I Pick Prime Numbers For My Security, How Fast Will I Find Them, and How Safe Are They?

Many of our public key methods rely on prime numbers, as they have wonderful properties, including a way of performing mathematical operations on numbers, but constrain them with a finite field (and where our maximum number is the prime number less one). The difficulty in RSA, for example, is to factorize the value of N into the two prime numbers which created N. If these are found, we can easily find out the decryption key associated with the encryption key [here].

The Greek mathematician Euclid showed that there is no “largest” prime number, and we can go onto infinity and never find the last prime.

So if we pick a prime number of a certain size, how do we know how many prime numbers that an intruder has to search through to find the one (or ones) we have used? If we select a small value, such as between 0 and 15 (4 bits), it is not going to be difficult, as the prime numbers will be:

2, 3, 5, 7, 11, 13, 17 and 19

But if we pick 10⁵⁰ how can we estimate the number of prime numbers there are. Well in cryptography we can use the pi(x), function to estimate the number of primes between 0 and x.

One of the simplest methods of calculating π(x) is to generate them and count. The following code…