Proven Primes

[Ben Laurie]

Anton Stiglic wrote:
> ----- Original Message ----- From: "Ben Laurie" <ben at algroup.co.uk> 
> To: "Cryptography" <cryptography at wasabisystems.com> 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 majordomo at wasabisystems.com