Probabilistic Primality Testing

An exceedingly common question asked in coding interviews is to write a function, method, algorithm, whatever to determine if a number is prime. Prime numbers have a wide range of applications in computer science, particularly with regard to cryptography. The idea is that factoring large numbers into their prime factors is extremely difficult.

“Because both the system’s privacy and the security of digital money depend on encryption, a breakthrough in mathematics or computer science that defeats the cryptographic system could be a disaster. The obvious mathematical breakthrough would be the development of an easy way to factor large prime numbers.” -Bill Gates, The Road Ahead

Granted, for most programming positions, this question is asked not to test the candidate’s knowledge of determining primality, but rather as an exercise to gain insight into his or her thought process on a well-understood problem.

The Naive Approach

The common approach to this problem is a simple brute-force solution. That is, divide the number {n} by every integer from 2 to n-1 and check the remainder. This is certainly the easiest way to solve the problem.

This is also incredibly inefficient. We can improve it a bit by checking factors from 2 to n/2, but that still isn’t very good for huge numbers. If n is composite (i.e. it’s not prime), then it can be factored into two numbers, one of which must be less than or equal to \sqrt{n}. With this in mind, we can improve our algorithm even further.

These are the solutions your interviewer will probably be looking for, starting with the most naive approach and improving from that, but even the revised version is not very efficient.

Probabilistic Testing

A slightly more sophisticated way to go about checking primality is to use probabilistic testing. Probabilistic tests use numbers, a, chosen at random from some sample space. This technique introduces a probability of error which can be reduced by repeating the test with independently selected a values.

There are a number of different probabilistic primality tests, some better than others.  One of the more simple probabilistic primality tests is the Fermat primality test, which is based on Fermat’s little theorem and is used in PGP and RSA encryption. The theorem states that, if p is prime, then a^{p-1} \equiv 1 \pmod{p} where 1\leq a < p.

This method will indicate if p is a probable prime, but since we’re only selecting a single a value, the possibility of p being incorrectly identified as a prime is high. In such situations, a is referred to as a Fermat liar. As suggested earlier, we can minimize this probability by repeating the process k times and selecting k witnesses.

This allows us to improve the probability of correctly determining the primality of p by performing k iterations, in which the probability of error becomes vanishingly small for large values of k. Nonetheless, being probabilistic in nature, this algorithm is inherently nondeterministic, which is really just a fancy way of saying we can get different results on different runs for the same input.

Polynomial, Deterministic Algorithms

Only within the last decade has a deterministic, polynomial-time algorithm for testing primality been developed. In 2002, the AKS primality test was discovered, moving primality into the P complexity class. The algorithm determines if a given number is prime or composite in polynomial time, and it’s the first to be simultaneously general, polynomial, unconditional, and deterministic. Try busting that out at an interview.

For the mathematically inclined (of which I do not consider myself), primality presents some interesting uses and even more interesting problems. It’s remarkable that a fast, deterministic solution for such a well-defined problem was found only in the last 10 years, and it makes you wonder what tough problems will be solved in the next 10 years and beyond.