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