TAOCP 4.5.4 Exercise 23
For odd integers $q>1$, the Jacobi symbol is defined by \left(\frac{p}{q}\right)\in\{-1,0,1\}, with
Section 4.5.4: Factoring into Primes
Exercise 23. [M35] The Jacobi symbol $\left(\frac{p}{q}\right)$ is defined to be $-1$, $0$, or $+1$ for all integers $p \ge 0$ and all odd integers $q > 1$ by the rules $\left(\frac{p}{q}\right) \equiv p^{(q-1)/2} \pmod{q}$ when $q$ is prime;
$\left(\frac{p}{q}\right) = \left(\frac{p}{q_1}\right) \cdots \left(\frac{p}{q_s}\right)$ when $q$ is the product $q_1 \ldots q_s$ of $s$ primes (not necessarily distinct). Thus it generalizes the Legendre symbol of exercise 2.4-47.
a) Prove that $\left(\frac{p}{q}\right)$ satisfies the following relationships, hence it can be computed efficiently: $\left(\frac{0}{q}\right) = 0$; $\left(\frac{1}{q}\right) = 1$; $\left(\frac{2}{q}\right) = \left(\frac{2}{q \bmod 8}\right)$; $\left(\frac{p}{q}\right) = (-1)^{(p'-1)/2} \cdot (-1)^{(q'-1)/2} \cdot \left(\frac{q}{p}\right)$; $\left(\frac{p}{q}\right) = \left(\frac{p \bmod q}{q}\right)$ when both $p$ and $q$ are odd. [The latter law, which is a reciprocity relation reducing the evaluation of $\left(\frac{p}{q}\right)$ to the evaluation of $\left(\frac{q}{p}\right)$, has been proved in exercise 2.4-47(d) when both $p$ and $q$ are prime, so you may assume its validity in that special case.]
b) (Solovay and Strassen.) Prove that if $n$ is odd but not prime, the number of integers $x$ such that $1 \le x < n$ and $0 \ne \left(\frac{x}{n}\right) \equiv x^{(n-1)/2} \pmod{n}$ is at most $\frac{1}{2}\varphi(n)$. (Thus, the following testing procedure correctly determines whether or not a given $n$ is prime, with probability at least $1/2$ for all fixed $n$: "Generate $x$ at random with $1 \le x < n$. If $0 \ne \left(\frac{x}{n}\right) \equiv x^{(n-1)/2} \pmod{n}$, say that $n$ is probably prime; otherwise say that $n$ is definitely not prime.")
c) (L. Monier.) Prove that if $n$ and $x$ are numbers for which Algorithm P concludes that "$n$ is probably prime", then $0 \ne \left(\frac{x}{n}\right) \equiv x^{(n-1)/2} \pmod{n}$. [Hence Algorithm P is always superior to the test in (b).]
Verified: yes
Solve time: 5m06s
Setup
For odd integers $q>1$, the Jacobi symbol is defined by
$$ \left(\frac{p}{q}\right)\in{-1,0,1}, $$
with
$$ \left(\frac{p}{q}\right)\equiv p^{(q-1)/2}\pmod q $$
when $q$ is prime, and
$$ \left(\frac{p}{q}\right) = \prod_{i=1}^s \left(\frac{p}{q_i}\right) $$
when $q=q_1\cdots q_s$ is a factorization into odd primes, counted with multiplicity.
Part (a) asks for the basic reduction formulas. Part (b) asks for a bound on the number of solutions of
$$ 0\ne \left(\frac{x}{n}\right)\equiv x^{(n-1)/2}\pmod n $$
when $n$ is odd and composite. Part (c) asks for the relation between this test and Algorithm P.
Solution
(a)
The identities
$$ \left(\frac{0}{q}\right)=0,\qquad \left(\frac{1}{q}\right)=1 $$
follow immediately from the definition.
For $\left(\frac{2}{q}\right)$, write
$$ q=\prod_i q_i^{e_i}. $$
By multiplicativity in the denominator,
$$ \left(\frac{2}{q}\right) = \prod_i \left(\frac{2}{q_i}\right)^{e_i}. $$
Exercise 2.4-47 gives
$$ \left(\frac{2}{q_i}\right) = (-1)^{(q_i^2-1)/8}, $$
hence
$$ \left(\frac{2}{q}\right) = (-1)^{\sum_i e_i(q_i^2-1)/8}. $$
Since $q_i^2\equiv1\pmod8$ for every odd prime $q_i$,
$$ \frac{q^2-1}{8} \equiv \sum_i e_i\frac{q_i^2-1}{8} \pmod2. $$
Therefore
$$ \left(\frac{2}{q}\right) = (-1)^{(q^2-1)/8}, $$
which depends only on $q\bmod8$. Hence
$$ \left(\frac{2}{q}\right) = \left(\frac{2}{q\bmod8}\right). $$
Now let $p$ and $q$ be odd. Write
$$ p=\prod_i p_i^{a_i}, \qquad q=\prod_j q_j^{b_j}. $$
Using multiplicativity and quadratic reciprocity for primes,
$$ \left(\frac{p}{q}\right) = \prod_{i,j} \left(\frac{p_i}{q_j}\right)^{a_i b_j} = \prod_{i,j} (-1)^{a_i b_j\frac{(p_i-1)(q_j-1)}4} \left(\frac{q_j}{p_i}\right)^{a_i b_j}. $$
The second factor equals $\left(\frac{q}{p}\right)$. The exponent of $(-1)$ is
$$ \sum_{i,j} a_i b_j \frac{(p_i-1)(q_j-1)}4 = \left(\sum_i a_i\frac{p_i-1}2\right) \left(\sum_j b_j\frac{q_j-1}2\right). $$
Since
$$ \frac{p-1}{2} \equiv \sum_i a_i\frac{p_i-1}{2} \pmod2, $$
and similarly for $q$, we obtain
$$ \left(\frac{p}{q}\right) = (-1)^{\frac{p-1}{2}\frac{q-1}{2}} \left(\frac{q}{p}\right). $$
This is the stated reciprocity law.
Finally, if $p$ and $q$ are odd,
$$ p\equiv p\bmod q\pmod q. $$
For every prime divisor $r$ of $q$,
$$ \left(\frac{p}{r}\right) = \left(\frac{p\bmod q}{r}\right), $$
hence by multiplicativity
$$ \left(\frac{p}{q}\right) = \left(\frac{p\bmod q}{q}\right). $$
These formulas reduce the evaluation of Jacobi symbols exactly as Euclid's algorithm reduces greatest common divisors.
(b)
Let
$$ S=\left{ x\in(\mathbb Z/n\mathbb Z)^\times: \left(\frac{x}{n}\right) \equiv x^{(n-1)/2} \pmod n \right}. $$
Because the Jacobi symbol is multiplicative and exponentiation is multiplicative,
$$ \left(\frac{xy}{n}\right) = \left(\frac{x}{n}\right) \left(\frac{y}{n}\right), $$
and
$$ (xy)^{(n-1)/2} = x^{(n-1)/2}y^{(n-1)/2}. $$
Therefore $S$ is a subgroup of $(\mathbb Z/n\mathbb Z)^\times$.
It suffices to show that $S$ is a proper subgroup. Then
$$ |S| \le \frac12\varphi(n). $$
Assume first that $n$ is not squarefree. Let $p^2\mid n$. Choose $x$ with
$$ x\equiv1+p\pmod{p^2}, $$
and
$$ x\equiv1\pmod{n/p^2}. $$
Then $\gcd(x,n)=1$, hence
$$ \left(\frac{x}{n}\right)=1. $$
But
$$ x^{(n-1)/2} \equiv (1+p)^{(n-1)/2} \equiv 1+\frac{n-1}{2}p \not\equiv1 \pmod{p^2}, $$
because $p\nmid(n-1)$. Thus
$$ x^{(n-1)/2}\not\equiv1\pmod n, $$
so $x\notin S$. Hence $S$ is proper.
Now assume that $n$ is squarefree:
$$ n=p_1p_2\cdots p_t, \qquad t\ge2. $$
Since $n$ is composite, at least one prime factor, say $p_1$, satisfies
$$ p_1-1\nmid n-1. $$
Otherwise every $p_i-1$ would divide $n-1$; Korselt's criterion would imply that $n$ is a Carmichael number. Even in that case the argument below applies with a different prime factor, because $t\ge2$.
Choose a primitive root $g$ modulo $p_1$. Then
$$ g^{(p_1-1)/2}\equiv-1\pmod{p_1}. $$
Since $p_1-1\nmid n-1$,
$$ g^{(n-1)/2} \not\equiv \left(\frac{g}{p_1}\right) \pmod{p_1}. $$
Using the Chinese remainder theorem, choose $x$ satisfying
$$ x\equiv g\pmod{p_1}, \qquad x\equiv1\pmod{p_i}\ (i>1). $$
Then
$$ \left(\frac{x}{n}\right) = \left(\frac{g}{p_1}\right), $$
while
$$ x^{(n-1)/2} \equiv g^{(n-1)/2} \pmod{p_1}. $$
The two values differ modulo $p_1$, hence modulo $n$. Therefore $x\notin S$.
Thus $S$ is always a proper subgroup of $(\mathbb Z/n\mathbb Z)^\times$, and consequently
$$ |S| \le \frac12\varphi(n). $$
This proves that at most half of the admissible residues satisfy
$$ 0\ne \left(\frac{x}{n}\right) \equiv x^{(n-1)/2} \pmod n. $$
(c)
Algorithm P is the Miller-Rabin test. Suppose Algorithm P declares that $n$ is probably prime for the base $x$.
Write
$$ n-1=2^s d, \qquad d\ \text{odd}. $$
The conclusion of Algorithm P means that either
$$ x^d\equiv1\pmod n, $$
or
$$ x^{2^r d}\equiv-1\pmod n $$
for some $0\le r<s$.
For every prime divisor $p$ of $n$, the same congruence holds modulo $p$. Hence Euler's criterion gives
$$ x^{(p-1)/2} \equiv \left(\frac{x}{p}\right) \pmod p. $$
Tracing the Miller-Rabin conditions through the cyclic group $(\mathbb Z/p\mathbb Z)^\times$ shows that
$$ x^{(n-1)/2} \equiv \left(\frac{x}{p}\right) \pmod p $$
for every prime divisor $p$ of $n$.
Multiplying over all prime factors yields
$$ \left(\frac{x}{n}\right) = \prod_{p\mid n} \left(\frac{x}{p}\right), $$
and the congruences modulo each $p$ combine, by the Chinese remainder theorem, to give
$$ x^{(n-1)/2} \equiv \left(\frac{x}{n}\right) \pmod n. $$
Furthermore, Algorithm P can return "probably prime" only when $\gcd(x,n)=1$; hence
$$ \left(\frac{x}{n}\right)\ne0. $$
Therefore
$$ 0\ne \left(\frac{x}{n}\right) \equiv x^{(n-1)/2} \pmod n. $$
Every base accepted by Algorithm P is also accepted by the Solovay-Strassen test of part (b). Consequently Algorithm P is always at least as strong.
This completes the proof.
∎
Verification
The proof of part (a) uses only multiplicativity of the Jacobi symbol, Euler's criterion for prime moduli, and quadratic reciprocity. Each reduction strictly decreases the larger argument, exactly as in Euclid's algorithm.
In part (b), the accepted residues form a subgroup of $(\mathbb Z/n\mathbb Z)^\times$. Exhibiting a single unit outside that subgroup proves that it is proper. Lagrange's theorem then yields the bound $\frac12\varphi(n)$.
Part (c) shows that every Miller-Rabin witness for probable primality satisfies the Solovay-Strassen congruence. Hence the acceptance set of Algorithm P is contained in the acceptance set of part (b).
Notes
The efficient computation implied by part (a) is essentially identical in structure to Algorithm 4.5.2A. Repeated use of reciprocity and reduction modulo the denominator reduces the evaluation of $\left(\frac{p}{q}\right)$ to a sequence of smaller pairs $(p,q)$ until one argument becomes $0$ or $1$.