Fermat's primality test vs. Miller-Rabin

[Joseph Ashwood]

----- Original Message ----- 
From: "Anton Stiglic" <astiglic at okiok.com>
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 majordomo at metzdowd.com