Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Dec 20, 2014 #1


    User Avatar
    Gold Member

    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
    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.
  2. jcsd
  3. Dec 21, 2014 #2


    User Avatar
    2017 Award

    Staff: Mentor

    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?).
  4. Dec 22, 2014 #3


    User Avatar
    Gold Member

    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.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Threads - Miller Rabin probability Date
Java Probably very easy question about isNaN() java Jan 10, 2017
How to interpret a complex Matrix as a Probability Matrix? Nov 22, 2016
Probability program equation in app. Jul 10, 2013
C++ and Probablities! Mar 12, 2013