In Miller-Rabin, what is the probability to get a witness?

  • Thread starter nomadreid
  • Start date
  • #1
nomadreid
Gold Member
1,560
168
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.
 

Answers and Replies

  • #2
35,925
12,762
I don't know about this specific algorithm, but often those numbers are hard to prove, so even if the real value might be very small (so small that Maple just uses 5 numbers), the proven upper limit can be much larger (1/4 here?).
 
  • Like
Likes nomadreid
  • #3
nomadreid
Gold Member
1,560
168
Thanks for the response, mfb. Given the limited amount known about primes and the infinity of possibilities, it is curious how they even came up with an upper limit.
 

Related Threads on In Miller-Rabin, what is the probability to get a witness?

Replies
1
Views
2K
Replies
2
Views
6K
  • Last Post
Replies
1
Views
1K
Replies
14
Views
1K
Replies
7
Views
3K
  • Last Post
Replies
3
Views
13K
Replies
4
Views
3K
Replies
3
Views
48K
Top