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.
Previous Page Next Page