In(adsbygoogle = window.adsbygoogle || []).push({});

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 anawhich is a strong liar forn."

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.

**Physics Forums - The Fusion of Science and Community**

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?

Loading...

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 |

**Physics Forums - The Fusion of Science and Community**