Historically, the first randomized algorithm was a method developed by Michael O. Rabin for the closest pair problem in computational geometry [REF].
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.