History
Historically, the first randomized algorithm was a method developed by Michael O. Rabin for the closest pair problem in computational geometry. The study of randomized algorithms was spurred by the 1977 discovery of a randomized primality test (i.e., determining the primality of a number) by Robert M. Solovay and Volker Strassen. Soon afterwards Michael O. Rabin demonstrated that the 1976 Miller's primality test can be turned into a randomized algorithm. At that time, no practical deterministic algorithm for primality was known.
The Miller-Rabin primality test relies on a binary relation between two positive integers k and n that can be expressed by saying that k "is a witness to the compositeness of" n. It can be shown that
- If there is a witness to the compositeness of n, then n is composite (i.e., n is not prime), and
- If n is composite then at least three-fourths of the natural numbers less than n are witnesses to its compositeness, and
- There is a fast algorithm that, given k and n, ascertains whether k is a witness to the compositeness of n.
Observe that this implies that the primality problem is in Co-RP.
If one randomly chooses 100 numbers less than a composite number n, then the probability of failing to find such a "witness" is (1/4)100 so that for most practical purposes, this is a good primality test. If n is big, there may be no other test that is practical. The probability of error can be reduced to an arbitrary degree by performing enough independent tests.
Therefore, in practice, there is no penalty associated with accepting a small probability of error, since with a little care the probability of error can be made astronomically small. Indeed, even though a deterministic polynomial-time primality test has since been found (see AKS primality test), it has not replaced the older probabilistic tests in cryptographic software nor is it expected to do so for the foreseeable future.
Read more about this topic: Randomized Algorithm
Famous quotes containing the word history:
“Anything in history or nature that can be described as changing steadily can be seen as heading toward catastrophe.”
—Susan Sontag (b. 1933)
“The history of all hitherto existing society is the history of class struggles.”
—Karl Marx (1818–1883)
“Whenever we read the obscene stories, the voluptuous debaucheries, the cruel and torturous executions, the unrelenting vindictiveness, with which more than half the Bible is filled, it would be more consistent that we called it the word of a demon than the Word of God. It is a history of wickedness that has served to corrupt and brutalize mankind.”
—Thomas Paine (1737–1809)