Proven Primes

Anton Stiglic astiglic at okiok.com
Thu Mar 6 10:37:51 EST 2003


----- 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.

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.

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.

--Anton





---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com



More information about the cryptography mailing list