38 1. Classical Computation

Ý

Ü

Ü Ä

Ü Ä

Fig. 4.1. The characteristic set of the predicate R(x, y). Vertical lines

represent the sets Sx.

(contains at most ε fraction of them). Therefore all values of x are divided

into two categories: for one of them L(x) is true and for the other L(x) is

false.

Remark 4.1. Probabilistic Turing machines (unlike nondeterministic ones,

which depend on almighty Merlin for guessing the computational path) can

be considered as real computing devices. Physical processes like the Nyquist

noise or radioactive decay are believed to provide sources of random bits; in

the latter case it is guaranteed by the very nature of quantum mechanics.

4.2. Primality testing. A classic example of a BPP problem is checking

whether a given integer q (represented by n = log2 q bits) is prime or not.

We call this problem Primality. We will describe a probabilistic primality

test, called Miller–Rabin test. For reader’s convenience all necessary facts

from number theory are given in Appendix A.

4.2.1. Main idea. We begin with a much simpler “Fermat test”, though

its results are generally inconclusive. It is based on Fermat’s little theorem

(Theorem A.9), which says that

if q is prime, then

aq−1

≡ 1 (mod q) for x ∈ {1,...,q − 1}.

We may regard a as a (mod q)-residue and simply write

aq−1

= 1, assuming

that arithmetic operations are performed with residues rather than integers.

So, the test is this: we pick a random a and check whether

aq−1

= 1.

If this is true, then q may be a prime; but if this is false, then q is not a

prime. Such a can be called a witness saying that a is composite. This kind

of evidence is indirect (it does not give us any factor of q) but usually easy

to find: it often suﬃces to check a = 2. But we will do a better job if we

sample a from the uniform distribution over the set {1,...,q − 1} (i.e., each

element of this set is taken with probability 1/(q − 1) ).