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

In practice, though, being in ${\mathbf{NP}}$ does not give a good way of solving the problem by itself; for that, we want the problem to be in ${\mathbf{P}}$. 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 ${\mathbf{BPP}}$: by definition, something belongs to the class ${\mathbf{BPP}}$ if there is a polynomial-time nondeterministic Turing machine such that on any computation, at least ${2/3}$ of the computation tree leads to the right answer. So the idea of ${\mathbf{BPP}}$ is that, to decide whether a string ${x}$ belongs to our language ${\mathcal{L}}$, we generate a bunch of random bits and then run a deterministic algorithm on the string ${x}$ 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 ${\mathbf{BPP} = \mathbf{P}}$ while ${\mathbf{P} \neq \mathbf{NP}}$. 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 ${N}$ is prime. As before, the algorithm will rely on a little elementary number theory.

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

$\displaystyle \left( \frac{M}{N} \right)$

for any ${M \in \mathbb{Z}}$. Recall that if ${N = \prod q_i}$ is a product of primes, then this is just the product of the usual quadratic symbols ${\prod \left( \frac{M}{q_i} \right)}$. When ${N}$ is a prime, then the fact that the group ${(\mathbb{Z}/N \mathbb{Z})^*}$ is cyclic implies that the quadratic symbol is given by

$\displaystyle \left( \frac{x}{N} \right) = x^{(N-1)/2},$

but this is not true in general. In fact:

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

We know that this holds if ${N}$ is prime. Conversely, let us suppose ${N}$ is composite. Then from the equality and the fact that the Jacobi symbol is always ${\pm 1}$, we find that ${x^{N-1} \equiv 1}$, implying ${N-1}$ is a period for the multiplicative group.

Suppose first ${N}$ is divisible by the square of a prime ${p}$. But this multiplicative group has order ${\phi(N)}$, which is divisible by ${p}$; thus ${(\mathbb{Z}/N\mathbb{Z})^*}$ has a subgroup of order ${p}$. But then the period cannot be ${N-1}$, which is prime to ${p}$.

Suppose next that ${N =\prod q_i}$ for the ${q_i}$ distinct primes. We can choose ${M}$ coprime to ${N}$ such that ${M}$ is congruent to a nonresidue ${r_1}$ mod ${q_1}$ and to ${1}$ mod ${q_i, i > 1}$ by the Chinese remainder theorem. Then the expression ${\left( \frac{M}{N} \right) = \prod \left( \frac{M}{q_i} \right)}$ shows that ${\left( \frac{M}{N} \right) = -1}$. If we reduce mod ${q_2}$, we get

$\displaystyle 1 \equiv -1 \mod q_2.$

This is a contradiction. In particular, we find:

Corollary 2 If ${N}$ is not prime, then for at least half of ${x \in (\mathbb{Z}/N\mathbb{Z})^*}$, we have

$\displaystyle \left( \frac{x}{N} \right) \neq x^{(N-1)/2}.$

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 ${N}$ is prime. Generate a random ${x \in [1, N-1]}$. Apply the euclidean algorithm to check whether ${x, N}$ are relatively prime; if not, return that ${N}$ is composite. Otherwise, compute the symbol ${\left( \frac{x}{N} \right)}$ and the power ${x^{(N-1)/2}}$; if they are equal, output yes, and if not, output no (composite). If ${N}$ is prime, the above algorithm will always output true. If ${N}$ is composite, the above algorithm will output false with probability ${\frac{1}{2}}$ at least. If we choose multiple ${x}$‘s randomly, we can make this probability better.

If we can show that this algorithm is efficient, then we will have seen that ${PRIMES \in \mathbf{BPP}}$. Now ${x^{(N-1)/2} \mod N}$ can be computed in polynomial time by the method of repeated squaring. The quadratic symbol can be computed by using the quadratic reciprocity law ${\left( \frac{M}{N} \right) \left( \frac{N}{M} \right)}$ (which is still true even if we don’t assume primeness) and the expression for ${\left( \frac{2}{N} \right) = (-1)^{(N^2 -1)/8}}$. Namely, to compute ${\left( \frac{M}{N} \right)}$ where ${M < N}$, we reduce this to computing ${\left( \frac{N}{M} \right)}$. But we can take the remainder of ${N}$ mod ${M}$ to compute this, and so are reduced to a smaller problem. So our algorithm runs pretty fast.