4. Probabilistic algorithms and the class BPP 39
Suppose q is composite. We want to know if the test actually shows that
with nonnegligible probability. Consider two cases.
1) gcd(a, q) = d = 1. Then
aq−1
0 1 (mod d), therefore
aq−1

1 (mod q). The test detects that q is composite. Unfortunately, the
probability to get such an a is usually small.
2) gcd(a, q) = 1, i.e. a
(Z/qZ)∗
(where
(Z/qZ)∗
denotes the group of
invertible (mod q)-residues). This is the typical case; let us consider it
more closely.
Lemma 4.2. If
aq−1
= 1 for some element a
(Z/qZ)∗,
then the Fermat
test detects the compositeness of q with probability 1/2.
Proof. Let G =
(Z/qZ)∗.
For any integer k define the following set:
G(m) = x G :
xm
= 1 . (4.2)
This is a subgroup in G (due to the identity
ambm
=
(ab)m
for elements
of an Abelian group). If
aq−1
= 1 for some a, then a / G(q−1), therefore
G(q−1) = G. By Lagrange’s theorem, the ratio |G| / |G(m)| is an integer,
hence |G| / |G(m)| 2. It follows that
aq−1
= 1 for at least half of a
(Z/qZ)∗.
And, as we already know,
aq−1
= 1 for all a /
(Z/qZ)∗.
Is it actually possible that q is composite but
aq−1
= 1 for all invert-
ible residues a? Such numbers q are rare, but they exist (they are called
Carmichael numbers). Example: q = 561 = 3 · 11 · 17. Note that the num-
bers 3 1, 11 1 and 17 1 divide q 1. Therefore
aq−1
= 1 for any
a
(Z/qZ)∗

=
Z3−1 × Z11−1 × Z17−1.
We see that the Fermat test alone is not sufficient to detect a composite
number. The Miller–Rabin test uses yet another type of witnesses for the
compositeness: if b2 1 (mod q), and b ±1 (mod q) for some b, then q is
composite. Indeed, in this case
b2
1 = (b 1)(b + 1) is a multiple of q but
b 1 and b + 1 are not, therefore q has nontrivial factors in common with
both b 1 and b + 1.
4.2.2. Required subroutines and their complexity. Addition (or sub-
traction) of n-bit integers is done by an O(n)-size circuit; multiplication and
division are performed by
O(n2)-size
circuits. These estimates refer to the
standard algorithms learned in school, though they are not the most efficient
for large integers. In the solutions to Problems 2.12, 2.13 and 2.14 we de-
scribed alternative algorithms, which are much better in terms of the circuit
depth, but slightly worse in terms of the size. If only the size is important,
the standard addition algorithm is optimal, but the ones for the multipli-
cation and division are not. For example, an O(n log n log log n)-size circuit
for the multiplication exists; see [5, Sec. 7.5] or [43, vol. 2, Sec. 4.3.3].
Previous Page Next Page