A strange thing has happened to me this semester. I’ve been spending more time thinking about physics and computer science than math! Granted, most of what I have been thinking about is pretty mathematical in nature, and I’ve tried to think of it that way if not.

So today in my algorithms class we were talking a bit about primality testing. It is, of course, necessary to know in practice if a given number of, say, {d} digits is prime, for instance to use the RSA algorithm. To do this efficiently, we want our algorithm to be polynomial in {d}. The existence of such an algorithm (the AKS algorithm) is fairly recent, and only appeared in 2002. But before that, partial results were known.

Let us consider the language {PRIMES} that consists of all {\left\{n: n \ \mathrm{is \ prime}\right\}}. Integers are represented in their binary expansion (or more generally their {k}-ary expansion where {k> 1}). The AKS algorithm shows that {PRIMES} lies in the complexity class {\mathbf{P}}.

It is straightforward to see that {PRIMES \in \mathbf{coNP}}; that is, there exist short certificates to show efficiently that a number is composite. This is easy: just take a factoring as the certificate. It was also shown in the 1970s by V. Pratt that succinct certificates for primality exist, or that {PRIMES \in \mathbf{NP}}. I would like to explain this result, which is of course immediate from the AKS algorithm, but which has an elegant approach of its own.

So, the idea of {\mathbf{NP}} is that given a number {n} of {d \simeq \log n} bits, I must be able to produce “evidence” of length polynomial in {d} that {n} is in fact prime. This evidence can be checked by a polynomial-time Turing machine. If I feed it the right proof for a given prime, this machine will return that it is convinced the number is prime. If I feed it a composite number and anything as its proof, then it will return no, no matter what.

Now the idea behind Pratt certificates is that a number {n} is prime if and only if the multiplicative group {(\mathbb{Z}/n\mathbb{Z})^*} is cyclic of order {n-1}. So if we can produce an element {a \in (\mathbb{Z}/n\mathbb{Z})} such that {a^{n-1} =1 } but {a^{(n-1)/p} \neq 1} for all primes {p \mid n}, then it will follow that {(\mathbb{Z}/n\mathbb{Z})^*} contains a cyclic group of order {n-1}. This will imply that {n} is prime, because otherwise {\phi(n) < n-1}.

Here is a way of convincing someone (or a machine) that a number {n} is prime. Exhibit a number {a \in \mathbb{Z}} (which will turn out to be a primitive root mod {n}) such that {a^{n-1} \equiv 1 \mod n} but {a^{(n-1)/p} \not\equiv 1\mod n} for each prime {p \mid n}. If you present the other person this data, she can check that you are not lying pretty efficiently: computing the mod {n} exponents {a^{n-1}, a^{(n-1)/p}} can be done in polynomial time (in {d} or {\log n}) by repeated squaring.

So the person can check that your choice of {a} was legitimate. What might be harder is to determine which {p}‘s to check for the {a^{(n-1)/p}}. A priori, we don’t know the other person can factor {n-1} efficiently. We need a little more for the certificate to be sound. Namely, we will need to include the prime factorization of {n-1} in the certificate so that the other person can check the {a^{(n-1)/p}}.

Of course, the other person will be able to check that the factorization is valid—just by multiplying the numbers together. It will be harder, though, for the other person to know that the numbers in the factorization that we are giving her are in fact prime. Namely, we need to produce evidence that each of the elements of the factorization are in fact prime! We can thus do this in the same way. So, if we want to convince someone that a number {n} is prime, here is the evidence we present:

  1. An integer {a}.
  2. A prime factorization of {n-1}
  3. (Inductively) prime certificates for every prime in the factorization of {n-1}.

Suppose inductively that the verifier has checked that every element in the factorization we have presented is in fact prime. The verifier will then check that {a^{n-1} \equiv 1 \mod n} and {a^{(n-1)/p} \not\equiv 1} for each prime {p} in the prime factorization. By the above observations, this verifier cannot be fooled.

So we now see that primality certificates exist and are efficient. It is clear that the above expression takes polynomial space, because there aren’t going to be too many primes that keep occurring in repeated factorizations. Computationally, though, if we wanted to find a given prime number, this is not helpful, as {\mathbf{NP}} is not (probably) a reasonable model of computation. We can be quickly convinced that a number is prime, but we don’t see how to find one ourselves.

It turns out that there is a simple and efficient probabilistic algorithm for doing so; that is, PRIMES belongs to the class BPP. Next time, I’ll explain this. And sometime later, maybe I’ll try to work through the AKS paper and explain that too.