Last time, I explained the MillerRabin probabilistic primality test. Let’s recall it:
Theorem. Let $p$ be an odd prime and write $p1 = 2^kq$ where $q$ is an odd number. If $a$ is relatively prime to $p$ then at least one of the following statements is true:
 $a^q\equiv 1\pmod{p}$, or
 One of $a^q,a^{2q},a^{4q},\dots,a^{2^{k1}q}$ is congruent to $1$ modulo $p$.
The MillerRabin randomized test looks for values of $a$ that don’t satisfy the conclusions of this theorem. Such an $a$ is called a witness. If such an $a$ can be found, then $n$ is composite. If no such $a$ is found after a bunch of iterations, then we consider $n$ to be probably prime.
For example, a hundred iterations of MillerRabin selected

42567145466394997389745925432816119242831606594464668684 93367494603397531278045340063840221007375464841971540619 22719704225243891237302105551862848741599320377952156121 9310096891044229934217756473496989664205519 
as a number that is most likely prime. A bruteforce factor testing to make sure that this number is prime would take many times the age of the universe. That’s pretty crazy! The MillerRabin test only takes a couple seconds, but how good is it really?
Now what about the percentage of witnesses for different numbers? Is this percentage close to 75%? In fact, although at least 75% of all possible bases are witnesses for any given composite number, often there are far more bases. In fact, only 0.6% of composite integers below 2000 have fewer than 90% of the total possible bases as witnesses. One such number is 1891 = 31*61. About 76% of possible bases are MillerRabin witnesses for 1891, which shows that the estimate of 75% is pretty good.
But for cryptographic applications, we’re not interested in finding composite numbers. Given a randomly selected odd composite number, we can say that the probability of the MillerRabin test failing to find it composite after $k$ iterations is at most $4^{k}$, which we can make very small very quickly. However, this conditional probability isn’t the same thing as the conditional probability that a randomly selected odd number is composite given that $k$iterations of MillerRabin thinks it is a prime!
A priori, it may be possible that the probability a number is composite given that $k$iterations of MillerRabin thinks it’s a prime is higher than $4^{k}$.
But this isn’t the case. Beauchemin, Brassard, Crépeau, Goutier, and Pomerance showed in a paper that this probability (that a randomly selected odd number is composite given $k$iterations of MillerRabin thinks it is a prime) is also at most $4^{k}$, assuming that the randomly selected odd numbers of sufficiently large (which thankfully is less than the typical modernday cryptographic application).