`----- 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 ofapplied cryptography: for t = 1 (one iteration) and for a 500-bitcandidate,we have probability p(X | Y_1) <= 2^-56, which is better than what youconcluded. (X representing the event that the candidate n is composite,Y_trepresenting 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 thatunder these conditions, the strong pseudoprime test does in fact muchbetterthan 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]