# Re: Fermat's primality test vs. Miller-Rabin

```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 :

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

 http://cvs.openssl.org/getfile/openssl/crypto/bn/bn.h?v=1.21

--
Regards,