It is well known that it's possible to fool Fermat test with Carmichael numbers. But, is it possible to deliberately fool many-rounded Miller-Rabin test by constructing some special number without using brute forcing strategy? I know that one round of Miller-Rabin distinguish with probability 25% that number is prime, but for many rounds brute force will become infeasible.


In fact even brute force does not work, unless you know what random numbers the Miller-Rabin test will use to test the numbers, because in case of each possible non-prime number, some Miller-Rabin test input will reveal it is composite.

FIPS 186-4 C.3 contains recommended Miller-Rabin number of rounds to use to test the numbers. Those amounts of Miller-Rabin tests are expected to catch composite numbers with overwhelmingly large probability. The document contains useful information about Miller-Rabin and how test is supposed to (probabilistically) protect from this attack (fooling it with composite numbers).

  • $\begingroup$ Thanks! I just checked openssl source, and it seems to generate random number for each round, as you said. $\endgroup$
    – catpnosis
    Jan 8 '14 at 7:12
  • $\begingroup$ Actually, the tests in FIPS 186-4 are tuned to be appropriate for random numbers (or ones generated from a benign source) - they don't assume that an adversary is selecting the numbers in an attempt to fool it. $\endgroup$
    – poncho
    Dec 10 '19 at 15:46

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.