Could Miller-Rabin primality test give false negative, for example when test prime number and gives it as composite?

I know that it could give false positive (giving composite number as prime), but I am not sure about the reverse.

  • 1
    $\begingroup$ A prime will always pass Miller-Rabin, at least in principle. $\endgroup$ – André Nicolas Nov 22 '15 at 8:00

No, it will not indicate composite when given a prime.

The Miller-Rabin test, like many primality tests, uses properties that are always true for primes, but are rarely true for composites. Hence, barring implementation defects, it will always return true (PROBABLY PRIME) when given a prime. Most composites will return false (DEFINITELY COMPOSITE). Some composites, which we call pseudoprimes to the particular test, will also return true.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.