----- Original Message ----- From: "Anton Stiglic" <[EMAIL PROTECTED]>
Subject: RE: Fermat's primality test vs. Miller-Rabin

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

My own tests disagreed with this, 512-bits seemed to have a threshhold around 70 passes for random candidates, I'm thinking you forgot a sieving step there (which would change the number substantially).

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.

I think much of the problem is the way the number is being applied. Giving a stream of random numbers that have passed a single round of MR you will find that very close to 50% of them are not prime, this does not mean that it passes 50% of the numbers (the 2^-80 probability given above is of this type). In fact it appears that integers fall on a continuum of difficulty for MR, where some numbers will always fail (easy composites), and other numbers will always pass (primes). The problem comes when trying to denote which type of probability you are discussing. What are the odds that a random 512-bit composite will be detected as composite by MR in one round? I don't think anyone has dependably answered that question, but the answer is very different from 1-(probability that MR-* says it's a prime)^-k. Any discussion needs to be more accurately phrased.

For example, my phrasing is that in the tests that I performed 50% (+/- experimental noise) of those numbers that passed a single round of MR also passed 128 rounds, leading me to conclude that 50% of the numbers that passed a single round of MR are in fact prime. Since each number that passed a single round was subjected to 127 additional rounds, a number of additional statistics can be drawn, in particular that of those that failed at least one round none failed less than 40 rounds, and that few passed less than 40 rounds. Due to the fact that this was only iterated 65536 times there is still substantial experimental error available. These pieces of information combined indicate that for 512-bits it is necessary to have 80 rounds of MR to verify a prime. Joe

The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]

Reply via email to