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


>
>>Ok after making that change, and a few others. Selecting only odd numbers
>>(which acts as a small seive) I'm not getting much useful information. It
>>appears to be such that at 512 bits if it passes once it passes 128 times,
>>and it appears to fail on average about 120-130 times, so the sieve
>>amplifies the values more than expected. Granted this is only a test of 
>>the
>
>>generation of 128 numbers, but I got 128 primes (based on 128 MR rounds).
>
>
> O.k., so if I read this right, your new results concord with the analysis 
> of
> Pomerance et al.   That would make much more sense.
>
> When you say "on average about 120-130 times the test fails", out of how
> many is that?

I should've said that the the quantity of numbers that failed the first test 
between each success was about 120-130. Apparently, even sieving based 
solely on "is it odd" is enough to substantially influence the outcome.
                Joe 



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