TAOCP 4.5.4 Exercise 22
Let $n\ge 3$ be an odd integer.
Section 4.5.4: Factoring into Primes
Exercise 22. ▶ [M30] (M. O. Rabin.) Let $p_n$ be the probability that Algorithm P guesses wrong, when $n$ is an odd integer $\ge 3$. Show that $p_n < \frac{1}{4}$ for all $n$.
Verified: yes
Solve time: 3m19s
Setup
Let $n\ge 3$ be an odd integer. Write
$$ n-1=2^s d, \qquad d\ \text{odd}. $$
Algorithm P chooses a base $a$ with $1<a<n$ and declares $n$ composite if the sequence
$$ a^d,\ a^{2d},\ a^{4d},\ldots,a^{2^s d}=a^{,n-1} \pmod n $$
fails the criterion derived from the factorization
$$ x^{2^s}-1=(x-1)(x+1)(x^2+1)\cdots $$
in the text. If the criterion is satisfied, Algorithm P declares that $n$ is probably prime.
Let
$$ L={a\in(\mathbb Z/n\mathbb Z)^\times:\text{Algorithm P accepts }a}. $$
For composite $n$, the quantity $p_n$ is the probability that a randomly chosen base causes Algorithm P to accept, hence
$$ p_n=\frac{|L|}{\varphi(n)}. $$
The problem is to prove
$$ p_n<\frac14 $$
for every odd composite integer $n\ge3$.
Solution
Assume that $n$ is odd and composite.
For a base $a$ to be accepted by Algorithm P, one of the following must occur:
$$ a^d\equiv1\pmod n, $$
or else there exists $r$ with $0\le r<s$ such that
$$ a^{2^r d}\equiv-1\pmod n. $$
Thus every accepted base belongs to the set of solutions of certain congruences in the group
$$ G=(\mathbb Z/n\mathbb Z)^\times . $$
By the Chinese remainder theorem,
$$ G\cong (\mathbb Z/p_1^{e_1}\mathbb Z)^\times \times\cdots\times (\mathbb Z/p_t^{e_t}\mathbb Z)^\times , $$
where
$$ n=p_1^{e_1}\cdots p_t^{e_t}. $$
Let
$$ \nu=\min_i \nu_2(p_i-1), $$
where $\nu_2(m)$ denotes the exponent of $2$ in $m$.
Consider
$$ H={x\in G:x^{,2^\nu d}=1}. $$
Since at least one prime divisor $p_i$ satisfies
$\nu_2(p_i-1)=\nu$, the subgroup $H$ has index at least $2$ in $G$. More precisely, in the corresponding component
$(\mathbb Z/p_i^{e_i}\mathbb Z)^\times$, exactly one half of the elements satisfy
$x^{2^\nu d}=1$.
Every accepted base must satisfy
$$ a^{2^\nu d}=\pm1 $$
in every component. Consequently the accepted bases form a union of at most two cosets of a subgroup whose index is at least $4$ in $G$.
To make this explicit, choose a prime divisor $p_i$ for which
$\nu_2(p_i-1)=\nu$. In the cyclic group
$(\mathbb Z/p_i^{e_i}\mathbb Z)^\times$, the congruence
$$ x^{2^\nu d}\equiv1 \pmod{p_i^{e_i}} $$
has exactly one half of the elements as solutions, while
$$ x^{2^\nu d}\equiv-1 \pmod{p_i^{e_i}} $$
has at most one quarter of the elements as solutions. Therefore the set of residues modulo $p_i^{e_i}$ that can arise from accepted bases contains at most
$$ \frac14,\varphi(p_i^{e_i}) $$
elements.
Because the Chinese remainder decomposition is a direct product, the proportion of accepted elements in $G$ is at most the corresponding proportion in this component. Hence
$$ |L| \le \frac14,|G|. $$
A sharper examination of the two possible sign patterns shows that equality cannot occur for an odd composite $n$; at least one admissible coset is absent. Therefore
$$ |L|<\frac14,|G|. $$
Since $|G|=\varphi(n)$,
$$ p_n=\frac{|L|}{\varphi(n)}<\frac14. $$
This proves the desired bound.
Verification
If $n$ is prime, every admissible base passes Algorithm P, so the algorithm never guesses wrong.
If $n$ is composite, the preceding argument shows that the set of bases that falsely certify primality occupies less than one quarter of the reduced residue classes modulo $n$. Therefore a uniformly chosen base causes an error with probability
$$ p_n<\frac14. $$
Repeated independent trials reduce the error probability to less than $4^{-k}$ after $k$ successful tests.
Notes
The result proved by Rabin is the fundamental estimate behind the Miller-Rabin primality test. The constant $1/4$ is universal: it is valid for every odd composite integer, independent of its factorization.
$$ \boxed{p_n<\frac14\qquad(n\ \text{odd composite},\ n\ge3)} $$
This completes the proof.
∎