Prime numbers are commonly used in the field of computer science and mathematics. They are one of those numbers that are so delightfully ubiquitous and interesting that I figured it's worth really digging into in a blog post.

What are prime numbers?

Prime numbers are numbers that have only two divisors, one and the number itself. Examples of prime numbers include 2, 3, 5, 7, and 11. There are infinitely many primes. As of writing this blog post (January 2020), the largest verified prime number is 2^82,589,933 − 1.

Where are prime numbers used?

Prime numbers are primarily used in cryptography. For example, RSA encryption, a popular encryption algorithm uses prime numbers in its implementation. To generate a public key, the RSA algorithm starts with two large random numbers, p and q, and uses those to derive a third number that is used to generate the public key.

The RSA encryption algorithm uses to large prime number because larger primes produce larger products when multiplied. In order to figure out the two prime numbers that multiplied to a particular number, you have to compute the prime factorization, which can take quite a long time for larger numbers.

Although the prime numbers in RSA encryption are used to generate a public key that is shared publicly, the actual prime numbers themselves are not share so no one can "spoof" a particular public key. The fact that it is hard to compute prime factorizations for large numbers ensures that it is not possible for some to reverse engineer the prime factors used to generate the public key.

In one of my previous blog posts, I discussed random numbers and how they are computed. As it turns out, prime numbers are useful when generating random numbers as well. The Lehmer random number generator algorithm generates a random number as a function of a large prime number and a fixed integer.

Outside of cryptography and random number generation, prime numbers show up in lots of interesting places in nature. The most popular occurrences of prime numbers in nature is the emergence of the cicadas which happen at prime number-intervals to avoid colliding with periods in time where there is a high density of predators.

How can you tell if a number is prime?

That's the million dollar question!

It's rather difficult to determine whether a number is prime or not. There's a word for describing the property of a number being prime or not: primality.

There are several different strategies for determining the primality of a number. The key distinction between one algorithm for determining primality and another are performance and accuracy.

The slowest algorithm for determining primality uses trial division. Given a number n, trial division will evaluate numbers from 2 to the square root of n and determine if any of these numbers evenly divides into n. If none do, then n is prime. If there is a number that n divided by in that range, then n is composite.

Why do we only evaluate the range from 2 to the square root of n?

Well, on the lower end, knowing that a number is divisible by 1 is not useful for determining whether it is composite or prime since both numbers are divisible by 1.

On the upper end, we leverage the fact that any composite number will have a set of at least two prime factors. Prime factors are prime numbers that when multiplied together will equal the composite number. If we can't find any prime factors for a number, then we know it is not a composite number. Since the smallest number of prime factors a composite number can have is 2, there is some prime number, p, that when multiplied with itself will equal n.

In addition to the trial division strategy for evaluating primality, there exists another class of strategies for determining whether or not a number is prime, known as probabilistic primality tests.

Generally, these tests will validate that a given number (let's call it p) is prime by selecting a random number (let's call it a) and applying some test between p and a. Depending on the result of the test, the algorithm will consider p either prime or composite. Most probabilistic algorithms will run multiple iterations using different values for a until it is sensible to declare that p is a prime.

So that's that on prime numbers. Similar to random numbers, one of the most interesting things about the intersection between prime numbers and computing is how algorithms, like those in cryptography, are able to exploit the properties of prime numbers to their benefit. Neat stuff!