The Miller–Rabin (or Rabin-Miller) primality test is an algorithm that determines whether a given number is prime.
Is it possible to construct a number that will pass an arbitrary number of Miller-Rabin and Rabin-Miller test rounds?
This Generating Strong Prime Numbers Report paper has test numbers that pass 20 rounds of MR.
I would like a general method test number that can pass $n$ (for example, $n = 50$) rounds, if such a thing is possible.
Thanks for any insights.
Best Answer
The question is a bit misguided. Miller Rabin uses a combination of Fermat's Little Theorem and Chinese Division Theorem to promise that a false prime for any number is not returned with a probability of more than 25%. So for any given composite number at least 3 tries out of 4 with a single test MR will report it as composite. http://rosettacode.org/wiki/Talk:Carmichael_3_strong_pseudoprimes,_or_Miller_Rabin%27s_nemesis#Analysis examines the behaviour for a range of numbers. Note that for 703 (19*37) MR will report it as possibly prime 22.86% of the time with 1 try. So with 10 tries it will report it incorrectly 1 in a million times. See http://rosettacode.org/wiki/Talk:Miller-Rabin_primality_test. Note that for most composites the probability is much less than 25%. So the answer is that finding a number which meets your requirement is simple. Any prime will do, no composite will. I think that the confusion is that the paper suggests that these seven numbers are composite. Dong is wong they are not. The chances of finding an MR pseudoprime is the same as finding a left over plesiosaur in Loch Ness, they are both mythical. Dong didn't find 7 for his class project, these numbers are prime.