4. Probabilistic algorithms and the class BPP 41

Remark 4.2. To get a probabilistic algorithm in sense of Definition 4.1,

we repeat this test twice: the probability of an error (a composite number

being undetected twice) is at most 1/4 1/2.

Proof of Theorem 4.3. As we have seen, the algorithm always gives the

answer “prime” for prime q.

Assume that q is composite (and odd). If gcd(a, q) 1 then Test 1

shows that q is composite. So, we may assume that that a is uniformly

distributed over the group G =

(Z/qZ)∗.

We consider two major cases.

Case A: q =

pα,

where p is an odd prime, and α 1. We show

that there is an invertible (mod q)-residue x such that

xq−1

= 1, namely

x = (1 +

pα−1)

mod q. Indeed,

x−1

= (1 −

pα−1)

mod q,

and4

xq−1

≡ (1 +

pα−1)q−1

= 1 + (q −

1)pα−1

+ higher powers of p

≡ 1 −

pα−1

≡ 1 (mod q).

Therefore Test 1 detects the compositeness of q with probability ≥ 1/2 (due

to Lemma 4.2).

Case B: q has at least two distinct prime factors. Then q = uv, where u

and v are odd numbers, u, v 1, and gcd(u, v) = 1. The Chinese remainder

theorem (Theorem A.5) says that the group G =

(Z/qZ)∗

is isomorphic to

the direct product U × V , where U =

(Z/uZ)∗

and V =

(Z/vZ)∗,

and that

each element x ∈ G corresponds to the pair

(

(x mod u), (x mod v)

)

.

For any m we define the following subgroup (cf. formula (4.2)):

G(m)

=

xm

: x ∈ G = Im ϕm, where ϕm : x →

xm.

Note that

G(m)

= {1} if and only if G(m) = G; this is yet another way to

formulate the condition that

am

= 1 for all a ∈ G. Also note that if a is

uniformly distributed over G, then

am

is uniformly distributed over

G(m).

Indeed, the map ϕm : x →

xm

is a group homomorphism; therefore the

number or pre-images is the same for all elements of

G(m).

It is clear that

G(m)

∼

=

U

(m)

× V

(m).

Now we have two subcases.

Case 1. U

(q−1)

= {1} or V

(q−1)

= {1}. This condition implies that

G(q−1)

= {1}, so that Test 1 detects q being composite with probability at

least 1/2.

Case 2. U

(q−1)

= {1} and V

(q−1)

= {1}. In this case Test 1 is always

passed, so we have to study Test 2. Let us define two sequences of subgroups:

U

(l)

⊇ U

(2l)

⊇ · · · ⊇ U

(2kl)

= {1}, V

(l)

⊇ V

(2l)

⊇ · · · ⊇ V

(2kl)

= {1}.

4A

similar argument is used to prove that the group

(Z/pαZ)∗

is cyclic; see Theorem A.11.