>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 [EMAIL PROTECTED]