Page 485 - Discrete Mathematics and Its Applications

464 7 / Discrete Probability

do this, the PC manufacturer can test each chip in a batch to see whether it is good. However,
this requires n tests. Assuming that each test can be carried out in constant time, these tests
require O(n) seconds. Can the PC manufacturer determine whether a batch of chips has been
tested by the chip maker using less time?

Solution: We can use a Monte Carlo algorithm to determine whether a batch of chips has been
tested by the chip maker as long as we are willing to accept some probability of error. The
algorithm is set up to answer the question: “Has this batch of chips not been tested by the
chip maker?” It proceeds by successively selecting chips at random from the batch and testing
them one by one. When a bad chip is encountered, the algorithm answers “true” and stops. If
a tested chip is good, the algorithm answers “unknown” and goes on to the next chip. After
the algorithm has tested a specified number of chips, say k chips, without getting an answer of
“true,” the algorithm terminates with the answer “false”; that is, the algorithm concludes that
the batch is good, that is, that the chip maker has tested all the chips in the batch.
The only way for this algorithm to answer incorrectly is for it to conclude that an untested
batch of chips has been tested by the chip maker. The probability that a chip is good, but that
it came from an untested batch, is 1 − 0.1 = 0.9. Because the events of testing different chips
from a batch are independent, the probability that all k steps of the algorithm produce the answer
k
“unknown,” given that the batch of chips is untested, is 0.9 .
By taking k large enough, we can make this probability as small as we like. For example,
by testing 66 chips, the probability that the algorithm decides a batch has been tested by the
66
chip maker is 0.9 , which is less than 0.001. That is, the probability is less than 1 in 1000
that the algorithm has answered incorrectly. Note that this probability is independent of n, the
number of chips in a batch. That is, the Monte Carlo algorithm uses a constant number, or O(1),
tests and requires O(1) seconds, no matter how many chips are in a batch. As long as the PC
manufacturer can live with an error rate of less than 1 in 1000, the Monte Carlo algorithm will
save the PC manufacturer a lot of testing. If a smaller error rate is needed, the PC manufacturer
can test more chips in each batch; the reader can verify that 132 tests lower the error rate to less
than1in1,000,000. ▲

EXAMPLE 16 Probabilistic Primality Testing In Chapter 4 we remarked that a composite integer, that is, an
integer greater than one that is not prime, passes Miller’s test (see the preamble to Exercise 44
in Section 4.4) for fewer than n/4 bases b with 1 <b <n. This observation is the basis for
a Monte Carlo algorithm to determine whether an integer greater than one is prime. Because
large primes play an essential role in public-key cryptography (see Section 4.6), being able to
generate large primes quickly has become extremely important.
The goal of the algorithm is to decide the question “Is n composite?” Given an integer n
greater than one, we select an integer b at random with 1 <b <n and determine whether n
passes Miller’s test to the base b.If n fails the test, the answer is “true” because n must be
composite, and the algorithm ends. Otherwise, we perform the test k times, where k is a positive
integer. Each time we select a random integer b and determine whether n passes Miller’s test to
the base b. If the answer is “unknown” at each step, the algorithm answers “false,” that is, it says
that n is not composite, so that it is prime. The only possibility for the algorithm to return an
incorrect answer occurs when n is composite, and the answer “unknown” is the output at each
of the k iterations. The probability that a composite integer n passes Miller’s test for a randomly
selected base b is less than 1/4. Because the integer b with 1 <b <n is selected at random at
each iteration and these iterations are independent, the probability that n is composite but the
k
A number that passes algorithm responds that n is prime is less than (1/4) . By taking k to be sufficiently large, we
many iterations of a can make this probability extremely small. For example, with 10 iterations, the probability that
probabilistic primality
the algorithm decides that n is prime when it really is composite is less than 1 in 1,000,000.
test is called an industrial With 30 iterations, this probability drops to less than 1 in 10 , an extremely unlikely event.
18
strength prime,even
though it may be To generate large primes, say with 200 digits, we randomly choose an integer n with 200
composite. digits and run this algorithm, with 30 iterations. If the algorithm decides that n is prime, we