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.

Namely, we can assume first of all that is odd. Then it makes sense to talk about the *quadratic symbol*

for any . Recall that if is a product of primes, then this is just the product of the usual quadratic symbols . When is a prime, then the fact that the group is cyclic implies that the quadratic symbol is given by

but this is not true in general. In fact:

Lemma 1The equality \( \left( \frac{x}{N} \right) = x^{(N-1)/2} \) holds for all prime to if and only if is prime.

We know that this holds if is prime. Conversely, let us suppose is composite. Then from the equality and the fact that the Jacobi symbol is always , we find that , implying is a period for the multiplicative group.

Suppose first is divisible by the square of a prime . But this multiplicative group has order , which is divisible by ; thus has a subgroup of order . But then the period cannot be , which is prime to .

Suppose next that for the distinct primes. We can choose coprime to such that is congruent to a nonresidue mod and to mod by the Chinese remainder theorem. Then the expression shows that . If we reduce mod , we get

This is a contradiction. In particular, we find:

Corollary 2If is not prime, then for at least half of , we have

Indeed, we have two different group-homomorphisms, so the subgroup on which they agree is index at least two.

In this way, we do have a probabilistic algorithm for testing whether a number is prime. Generate a random . Apply the euclidean algorithm to check whether are relatively prime; if not, return that is composite. Otherwise, compute the symbol and the power ; if they are equal, output yes, and if not, output no (composite). If is prime, the above algorithm will always output true. If is composite, the above algorithm will output false with probability at least. If we choose multiple ‘s randomly, we can make this probability better.

If we can show that this algorithm is efficient, then we will have seen that . Now can be computed in polynomial time by the method of repeated squaring. The quadratic symbol can be computed by using the quadratic reciprocity law (which is still true even if we don’t assume primeness) and the expression for . Namely, to compute where , we reduce this to computing . But we can take the remainder of mod to compute this, and so are reduced to a smaller problem. So our algorithm runs pretty fast.

## Leave a Reply