Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question
up vote 5 down vote accepted

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).

share|improve this answer
Thanks! I just checked openssl source, and it seems to generate random number for each round, as you said. – catpnosis Jan 8 '14 at 7:12

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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