Michael O. Rabin analyzed a randomized algorithm for primality testing in his 1980 paper. The Miller-Rabin primality test checks whether a candidate integer satisfies conditions obeyed by primes under modular exponentiation. A failed check certifies compositeness; passing a check gives a probable prime, not a proof of primality.[ref]
For each fixed odd composite candidate, at most one quarter of the admissible bases are strong liars. Independent uniformly chosen bases therefore reduce the probability of accepting that composite to at most after rounds. This probability is over the test's choices for a fixed input; it is not a posterior probability that an arbitrary accepted integer is prime.
Articles by others on the same topic
Michael O. Rabin is an influential computer scientist known for his contributions to theoretical computer science, particularly in the areas of algorithms, cryptography, and randomization techniques. He is widely recognized for his work on the Rabin-Karp string search algorithm, which uses hashing for efficient substring searching, and for his contributions to randomized algorithms.