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