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 [EMAIL PROTECTED]