42 1. Classical Computation
Note that U
= {1} and V
= {1}. Specifically, both U
and V
the residues that correspond to −1. Indeed, both U and V contain −1, and
= −1 since l is odd.
Going from right to left, we find the first place where one of the sets
contains an element different from 1. It other words, we find
t =
such that 0 s k, U
= {1}, V
= {1}, and either U
= {1}
or V
= {1}.
We will prove that Test 2 shows (with probability at least 1/2) that q is
composite. By our assumption
= 1, so we need to know the probability
of the event
= ±1. Let us consider two possibilities.
Case 2a. One of the sets U
equals {1} (for example, let U
{1}). This means that for any a the pair
mod u),
mod v)
has 1 as
the first component. Therefore
= −1, since −1 is represented by the pair
(−1, −1).
At the same time, V
= {1}; therefore the probability that
has 1 in
the second component is at most 1/2 (by Lagrange’s theorem; cf. proof of
Lemma 4.2). Thus Test 2 says “composite” with probability at least 1/2.
Case 2b. Both sets U
and V
contain at least two elements: |U
c 2, |V
= d 2. In this case
has 1 in the first component with
probability 1/c (there are c equiprobable possibilities) and has 1 in the
second component with probability 1/d. These events are independent due
to the Chinese remainder theorem, so the probability of the event
= 1
is 1/cd. For similar reasons the probability of the event
= −1 is either
0 or 1/cd. In any case the probability of the event
= ±1 is at most
2/cd 1/2.
4.3. BPP and circuit complexity.
Theorem 4.4. BPP P/ poly.
Proof. Let L(x) be a BPP-predicate, and M a probabilistic TM that de-
cides L(x) with probability at least 1 ε. By running M repeatedly we
can decrease the error probability. Recall that a polynomial number of rep-
etitions leads to the exponential decrease. Therefore we can construct a
polynomial probabilistic TM M that decides L(x) with error probability
less that ε
for inputs x of length n.
The machine M uses a random string r (one random bit for each step).
For each input x of length n, the fraction of strings r that lead to an incorrect
answer is less than
Therefore the overall fraction of “bad” pairs (x, r)
among all such pairs is less than
[If one represents the set of all pairs
(x, r) as a unit square, the “bad” subset has area
It follows that
there exists r = r∗ such that the fraction of bad pairs (x, r) is less than
Previous Page Next Page