Could Miller-Rabin primality test give false negative, for example when test prime number and gives...
skylsn
Answered
2022-06-27
Could Miller-Rabin primality test give false negative, for example when test prime number and gives it as composite?
Answer & Explanation
America Barrera
Expert
2022-06-28Added 23 answers
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.
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.
Most Popular Questions
Aryanna Rowland
2022-03-16
Lizeth Herring
2022-12-30
talpajocotefnf3
2022-03-27
