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: Probabilistic Complexity Theory
Famous quotes containing the word history:
“[Men say:] “Don’t you know that we are your natural protectors?” But what is a woman afraid of on a lonely road after dark? The bears and wolves are all gone; there is nothing to be afraid of now but our natural protectors.”
—Frances A. Griffin, U.S. suffragist. As quoted in History of Woman Suffrage, vol. 4, ch. 19, by Susan B. Anthony and Ida Husted Harper (1902)
“You that would judge me do not judge alone
This book or that, come to this hallowed place
Where my friends’ portraits hang and look thereon;
Ireland’s history in their lineaments trace;
Think where man’s glory most begins and ends
And say my glory was I had such friends.”
—William Butler Yeats (1865–1939)
“Every library should try to be complete on something, if it were only the history of pinheads.”
—Oliver Wendell Holmes, Sr. (1809–1894)