Jerrold Leichter wrote:
| > 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 choose random bases, the distribution is irrelevant. You do trust your
random number generator, don't you? :-)
Hmm. This is an excellent point.
--
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]
