Fermat's primality test vs. Miller-Rabin

Anton Stiglic astiglic at okiok.com
Tue Nov 15 19:55:25 EST 2005


>The general consensus is that for 500-bit numbers one needs only 6 MR
>tests for 2^{-80} error probability [1]:

>... 

> and thus a single test gives ~2^{-13}.

If you just took the exponent 80 and divided it by 6 to get ~13, I don't
think that is the right reasoning.  Look at table 4.3 of the Handbook of
applied cryptography: for t = 1 (one iteration) and for a 500-bit candidate,
we have probability p(X | Y_1) <= 2^-56, which is better than what you
concluded.  (X representing the event that the candidate n is composite, Y_t
representing the event that Miller-Rabin(n, t) declares n to be prime).

The results in table 4.3 and 4.4 of HAC are for randomly (uniform) chosen
candidates, and I think you need to do a basic sieving (don't remeber if
that is necessary, but I think it is).  The result is due to the fact that
under these conditions, the strong pseudoprime test does in fact much better
than 1/4 probability of error ( value of P(Y_t | X) is very low ), this
result is due to Damgard, Landrock and Pomerance, based on earlier work of
Erdos and Pomerance.

--Anton


---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com



More information about the cryptography mailing list