----- Original Message ----- From: "Ben Laurie" <[EMAIL PROTECTED]> To: "Cryptography" <[EMAIL PROTECTED]> Sent: Thursday,
March 06, 2003 6:47 AM Subject: Proven Primes
I'm looking for a list or lists of sensibly sized proven primes - all the lists I can find are more interested in records, which are _way_ too big for cryptographic purposes.
I'm not aware of such a list. If you can't find any you can generate
the list yourself using ECPP (Elliptic Curve Primality Proving), an implementation of which is available here http://www.lix.polytechnique.fr/~morain/Prgms/ecpp.english.html The
result of ECPP is guaranteed (no probability of error), and provides
a certificate of primality for integers that are proven to be prime. A competing algorithm is the Jacobi Sums test, but it is much more complicated, so implementation errors are not to be disregarded, with
ECPP the verification of a primality certificate is simple to
implement, so you can make sure that there were no errors in the
implementation of the proving algorithm.
I'm not convinced any of those binaries are going to run on my system (which is FreeBSD), and anyway, if I'm going to use a binary to do ECPP I may as well shove it through Mathematica - much prettier UI :-)
Is their no free implementation of ECPP? Is there at least a free verifier?
There is also the new algorithm by Agrawal, Kayal and Saxena, but I don't believe that it is efficient in practice for the sizes of integers you are looking at. Also note that if you assume the Extended Riemann Hypothesis (ERH) to be true, you can use the Miller-Rabin algorithm in a deterministic fashion in polynomial time with no probability error.
Oh?
The ECPP package is easy to use and fast. The site gives benchmarks for proving 512-bit primes: Pentium III (450MHz) 4.4 sec Solaris 5.7 9.5 sec Alpha EV56 (500MHz) 4 sec
I suggest you generate potential Sophie Germain primes q using your favorite library (I use OpenSSL for example) and then use the ECPP package to verify that in fact both q and 2q + 1 are really prime.
Sounds like a plan. Thanks very much for the info.
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]
