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

  • Thread starter nomadreid
  • Start date
  • Tags
    Probability
In summary, the Miller-Rabin Primality test has a 3/4 chance of correctly identifying a non-prime number, as stated in the introductory post by Jeremy Kun. However, the Wikipedia page on the same topic notes that there is still a small chance of encountering a "strong liar" that would yield an incorrect result. The value of 3/4 may seem arbitrary, but it is based on the limited knowledge currently available on prime numbers and the potential infinite possibilities. Despite this, by running enough tests, the probability of encountering a liar can be reduced as close to zero as desired. The upper limit of 1/4 may seem high, but it is a proven value and can be significantly lower than the actual probability.
  • #1

nomadreid

Gold Member
1,662
203
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.
 
Technology news on Phys.org
  • #2
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
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.
 

1. What is a witness in the Miller-Rabin algorithm?

A witness in the Miller-Rabin algorithm is a number that is used to determine whether a given number is a prime or a composite number. A witness is chosen randomly and is used to perform a series of calculations that help to determine the probability that the given number is a prime.

2. How is the probability to get a witness calculated in the Miller-Rabin algorithm?

The probability to get a witness in the Miller-Rabin algorithm is calculated using a formula that takes into account the number of iterations performed, the value of the given number, and the number of witnesses chosen. The probability increases with the number of iterations and decreases with the number of witnesses chosen.

3. What is the significance of the probability to get a witness in the Miller-Rabin algorithm?

The probability to get a witness is significant as it determines the accuracy of the Miller-Rabin algorithm in identifying prime numbers. A higher probability means a higher chance of correctly identifying a prime number, while a lower probability may lead to incorrect results.

4. How does the probability to get a witness affect the efficiency of the Miller-Rabin algorithm?

The probability to get a witness has a direct impact on the efficiency of the Miller-Rabin algorithm. A higher probability means that fewer iterations and witnesses are required to accurately determine the primality of a given number, making the algorithm more efficient. On the other hand, a lower probability may require more iterations and witnesses, resulting in a longer computation time.

5. Can the probability to get a witness be adjusted in the Miller-Rabin algorithm?

Yes, the probability to get a witness can be adjusted in the Miller-Rabin algorithm by changing the number of iterations and witnesses used. Increasing the number of iterations and witnesses will result in a higher probability, while decreasing them will result in a lower probability. However, it is crucial to strike a balance between accuracy and efficiency when adjusting the probability to get a witness.

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

Back
Top