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. (more…)