Solovay-Strassen primality testing algorithm

Let ${\mathbb{Z}}_n^*$ be the set of integers $1\leq a\le n$ such that ${\rm gcd}(a,x)=1$. Recall that the Euler phi function is defined by $\varphi(n)=\vert{\mathbb{Z}}_n^*\vert$.

Definition 1.1   Let $p$ be an odd prime. For $a\in{\mathbb{Z}}$, the Legendre symbol ${\displaystyle\genfrac{(}{)}{}{}{a}{p}}$ is defined as follows.

$$% latex2html id marker 1641{\displaystyle\genfrac{(}{)}{}{... ... x)(x^2\equiv a\pmod{p})\\ -1 & \mbox{otherwise}. \end{array}$$

In the second case we say that $a$ is a quadratic residue mod $p$; in the third case, $a$ is a nonresidue mod $p$. Note that 0 is not a quadratic residue even though $0^2=0$.

Theorem 1.2   Let $p,q$ be odd primes. The Legendre symbol satisfies the following identities.

(1)

If $a\equiv b\pmod p$ then ${\displaystyle\genfrac{(}{)}{}{}{a}{p}}={\displaystyle\genfrac{(}{)}{}{}{b}{p}}$.

(2)

${\displaystyle\genfrac{(}{)}{}{}{ab}{p}}={\displaystyle\genfrac{(}{)}{}{}{a}{p}}{\displaystyle\genfrac{(}{)}{}{}{b}{p}}$;

(3)

${\displaystyle\genfrac{(}{)}{}{}{-1}{p}}=(-1)^{(p-1)/2}$;

(4)

${\displaystyle\genfrac{(}{)}{}{}{2}{p}}=(-1)^{(p^2-1)/8}$;

(5)

${\displaystyle\genfrac{(}{)}{}{}{p}{q}}={\displaystyle\genfrac{(}{)}{}{}{q}{p}} (-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}$ (this identity, observed by Euler and Legendre and proved by Gauss, is called Quadratic Reciprocity);

Definition 1.3   Let $a$ be an integer and $b$ be an odd integer. Let $b=\prod_{i=1}^{\ell} p_i^{k_i}$ be the factorization of $b$. The Jacobi symbol ${\displaystyle\genfrac{(}{)}{}{}{a}{b}}$ is defined as follows.

$${\displaystyle\genfrac{(}{)}{}{}{a}{b}}=\prod_{i=1}^{\ell}{\displaystyle\genfrac{(}{)}{}{}{a}{p_i}}^{k_i},$$

where the right hand side of the definition uses the Legendre symbol.

Recall that Euclid's algorithm computes the greatest common divisor of integers $a,b$, using

$${\rm gcd}(a,b)= {\rm gcd}(b\ {\rm mod}\ a,a).$$ (1)

Theorem 1.4   Let $N$ be an integer. Assume that $N$ is not a prime and that $N$ is not $m^k$ for some $k\geq 2$. Then there exists $a\in{\mathbb{Z}}_N^*$ such that

$${\displaystyle\genfrac{(}{)}{}{}{a}{N}}\not\equiv a^{(N-1)/2}\pmod{N}.$$ (2)

Theorem 1.13, and Exercises 1.11, 1.12, 1.14, 1.15 give us a polynomial-time randomized algorithm which on input $N$,

• if $N$ is composite
  • with probability $\geq 1/2$ outputs a proof that $N$ is composite,
  • otherwise outputs "don't know";
• if $N$ is prime, always outputs "don't know."

Amplification. Note that by repeating this algorithm $k$ times with independent coin flips, the probability that we never find a proof of compositeness when $N$ is composite is reduced to $\le 1/2^k$, so if we get ``don't know'' each time, it is a safe bet that $N$ is prime. (How safe?)