GILA 3: Probabilistic algorithms for primality testing

Last time, we showed that prime numbers admit succinct certificates. Given a number containing bits, one could produce a “proof” that the number is prime in polynomial in space. In other words, the language containing all primes (represented in the binary expansion, say) lies in the complexity class .

In practice, though, being in does not give a good way of solving the problem by itself; for that, we want the problem to be in . Perhaps, though, that is too strict. One relaxation is to consider classes of problems that can be solved by randomized algorithms that run in polynomial time—randomized meaning that the right output comes out with high probability, that is. This is the class : by definition, something belongs to the class if there is a polynomial-time nondeterministic Turing machine such that on any computation, at least of the computation tree leads to the right answer. So the idea of is that, to decide whether a string belongs to our language , we generate a bunch of random bits and then run a deterministic algorithm on the string together with the random bits. Most likely, if the random bits were not too bad, we will get the right answer.

In practice, people tend to believe that while . But, in any case, probabilistic algorithms may be more efficient than deterministic ones, so even if the former equality holds they are interesting.

Today, I want to describe a probabilistic algorithm for testing whether a number is prime. As before, the algorithm will rely on a little elementary number theory.

 

GILA 2: Pratt certificates for primality

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, digits is prime, for instance to use the RSA algorithm. To do this efficiently, we want our algorithm to be polynomial in . 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 that consists of all . Integers are represented in their binary expansion (or more generally their -ary expansion where ). The AKS algorithm shows that lies in the complexity class .

It is straightforward to see that ; 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 . 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.

 

PRIMES

There is a new program called PRIMES for high school students in the Boston area. There are lots of high school math programs out there, but this one is fairly unique in offering a research experience. (RSI is the only one I know of, and PRIMES is based on it.) Also, unlike most of the others, it is during the school year as well–that’s why it’s only for kids in Boston.

Anyway, it looks like a very nice idea, and the mentor-in-charge, Pavel Etingof, has a fair bit of experience with this sort of thing. So if you’re a high school student in the area, apply! Or if you know one, tell them about it.