Fermat's primality test vs. Miller-Rabin

[Sidney Markowitz]

Joseph Ashwood wrote:
> Apparently, they are, I'm ran a sample, but even with the added second 
> sanity check, every one of them that passes a single round comes up prime.
> 
> I then proceeded to move it to 2048-bit numbers. It takes longer and the 
> gaps between primes is averaging around 700 right now, but once again if it 
> passes a single test it passes all 128+128

Ok, I did misunderstand you. If that "failed 120-130 times" is talking about
the number of trials between primes, then you are getting within the range of
expected results.

According to the prime number theorem, the probability of selecting a prime
number at random from odd numbers is about 2/ln(n) which for a 512 bit number
is about 1 in 177, which means you have about a 50% chance of 120 tries before
finding a prime.

According to the results that Anton quoted there is a 2^56 chance that a 512
bit odd number that passes one round of Miller-Rabin is actually prime.

So all of your results do make sense.

 -- sidney

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