- #1
nomadreid
Gold Member
- 1,739
- 235
In
http://jeremykun.com/2013/06/16/miller-rabin-primality-test/
which introduces the Miller-Rabin Primality test, it is stated
"If p is not a prime, then there is at least a 3/4 chance that a randomly chosen n will be a witness."
However, in
http://en.wikipedia.org/wiki/Miller–Rabin_primality_test
it is stated "There is, nevertheless, a small chance that we are unlucky and hit an a which is a strong liar for n."
Now, I suppose that 1/4 may be considered "small", and of course the first author said "at least", and anyway by running enough tests one can reduce the probability of liars as close to zero (without hitting zero) as one wishes (or equivalently of witnesses as close to one...), but nonetheless I am wondering whether "3/4" was not picked out of a hat, or whether it has a solid basis.
http://jeremykun.com/2013/06/16/miller-rabin-primality-test/
which introduces the Miller-Rabin Primality test, it is stated
"If p is not a prime, then there is at least a 3/4 chance that a randomly chosen n will be a witness."
However, in
http://en.wikipedia.org/wiki/Miller–Rabin_primality_test
it is stated "There is, nevertheless, a small chance that we are unlucky and hit an a which is a strong liar for n."
Now, I suppose that 1/4 may be considered "small", and of course the first author said "at least", and anyway by running enough tests one can reduce the probability of liars as close to zero (without hitting zero) as one wishes (or equivalently of witnesses as close to one...), but nonetheless I am wondering whether "3/4" was not picked out of a hat, or whether it has a solid basis.