Jerrold Leichter wrote:
| Apologies, slightly at cross-purposes here. For a start, Sophie Germain primes | are needed for D-H (or rather, safe primes), and secondly, I was talking about | proving arbitrary primes, rather than constructing provable primes.
>
Isn't *proving* primality rather overkill for the purpose at hand (which seems to be verifying that an alleged prime isn't a non-prime, sent to "spike" the system). Are there any known sets of numbers - much less ways to *choose* members of those sets - which will show up as prime with significant probability to Miller-Rabin? As far as I know, M-R has a *worst case* false positive rate of 1/4. Even a fairly small number of random M-R tests should make slipping in a non-prime less probable than a variety of other attacks.
There aren't any such sets known to me. Can I be sure there are none known to anyone? No.
Not sure I agree with the false positive rate. What is known is that 3/4 of the bases are strong witnesses for a composite number. But is it known that these are evenly distributed? I don't know, but that would be required for a 1/4 false positive rate.
If you want to go further, there's the Baille-PSW test (http://mathworld.wolfram.com/Baillie-PSWPrimalityTest.html) which it appears has no "false positives" for any integer of less than about 10,000 digits - way beyond what you would likely use in the near future.
Based on a statistical argument from a closed source prover and verifier. Hmm.
The point of proofs (at least, useful proofs) is that they produce certificates that are cheap to verify. So, yeah, sure it may be overkill, but I'll do the killing so you don't have to.
Cheers, Ben. -- http://www.apache-ssl.org/ben.html http://www.thebunker.net/ "There is no limit to what a man can do or how far he can go if he doesn't mind who gets the credit." - Robert Woodruff --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
