Fermat's primality test vs. Miller-Rabin

[Alexander Klimov]

On Fri, 11 Nov 2005, Joseph Ashwood wrote:
> From: "Charlie Kaufman" <charliek at exchange.microsoft.com>
>
> >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 majordomo at metzdowd.com