42 1. Classical Computation

Note that U

(l)

= {1} and V

(l)

= {1}. Specifically, both U

(l)

and V

(l)

contain

the residues that correspond to −1. Indeed, both U and V contain −1, and

(−1)l

= −1 since l is odd.

Going from right to left, we find the first place where one of the sets

U

(m),

V

(m)

contains an element different from 1. It other words, we find

t =

2sl

such that 0 ≤ s k, U

(2t)

= {1}, V

(2t)

= {1}, and either U

(t)

= {1}

or V

(t)

= {1}.

We will prove that Test 2 shows (with probability at least 1/2) that q is

composite. By our assumption

a2t

= 1, so we need to know the probability

of the event

at

= ±1. Let us consider two possibilities.

Case 2a. One of the sets U

(t),

V

(t)

equals {1} (for example, let U

(t)

=

{1}). This means that for any a the pair

(

(at

mod u),

(at

mod v)

)

has 1 as

the first component. Therefore

at

= −1, since −1 is represented by the pair

(−1, −1).

At the same time, V

(t)

= {1}; therefore the probability that

at

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

(t)

and V

(t)

contain at least two elements: |U

(t)|

=

c ≥ 2, |V

(t)|

= d ≥ 2. In this case

at

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

at

= 1

is 1/cd. For similar reasons the probability of the event

at

= −1 is either

0 or 1/cd. In any case the probability of the event

at

= ±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 ε

1/2n

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

1/2n.

Therefore the overall fraction of “bad” pairs (x, r)

among all such pairs is less than

1/2n.

[If one represents the set of all pairs

(x, r) as a unit square, the “bad” subset has area

1/2n.]

It follows that

there exists r = r∗ such that the fraction of bad pairs (x, r) is less than