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 suﬃcient 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 eﬃcient

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].