On Fri, 11 Nov 2005, Joseph Ashwood wrote: > From: "Charlie Kaufman" <[EMAIL PROTECTED]> > > >I've heard but not confirmed a figure of one failure in 20 million. I've > >never heard an estimate of the probability that two runs would fail to > >detect the composite. It couldn't be better than one failure is 20 million > >squared or worse than one in 80 million. > > I can confirm that that number of completely wrong. I just implemented a > small Java program to test exactly that. Each number was vetted by a single > pass of Miller-Rabin (iterations = 1). With 512-bit numbers the first 52 > random guesses that pass the first test resulted in 26 numbers that failed > to pass 128 iterations. I find it rather odd that this is exactly half, and > I also notice that of those that failed they almost all seem to have failed > at least half of them.

The general consensus is that for 500-bit numbers one needs only 6 MR tests for 2^{-80} error probability [1]: number of Miller-Rabin iterations for an error rate of less than 2^-80 for random 'b'-bit input, b >= 100 (taken from table 4.4 in the Handbook of Applied Cryptography [Menezes, van Oorschot, Vanstone; CRC Press 1996]; original paper: Damgaard, Landrock, Pomerance: Average case error estimates for the strong probable prime test. -- Math. Comp. 61 (1993) 177-194) #define BN_prime_checks(b) ((b) >= 1300 ? 2 : \ (b) >= 850 ? 3 : \ (b) >= 650 ? 4 : \ (b) >= 550 ? 5 : \ (b) >= 450 ? 6 : \ (b) >= 400 ? 7 : \ (b) >= 350 ? 8 : \ (b) >= 300 ? 9 : \ (b) >= 250 ? 12 : \ (b) >= 200 ? 15 : \ (b) >= 150 ? 18 : \ /* b >= 100 */ 27) and thus a single test gives ~2^{-13}. [1] http://cvs.openssl.org/getfile/openssl/crypto/bn/bn.h?v=1.21 -- Regards, ASK --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]