Re: Proven Primes

[Ben Laurie]

Bill Frantz wrote:
At 9:21 PM -0800 3/6/03, Ben Laurie wrote:

Bill Frantz wrote:

At 3:47 AM -0800 3/6/03, Ben Laurie wrote:


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.
By "sensibly sized" I mean in the range 512-8192 bits. I'm particularly
after Sophie Germain primes right now, but I guess all primes are of
interest.


Having set a computer to the problem of coming up with a Sophie Germain
prime for the E startup protocol (Diffie-Hellman),  I offer you:
   static final BigInteger g = new BigInteger("2");
   static final BigInteger modulus =
       new
BigInteger("11973791477546250983817043765044391637751157152328012"
                       +
"72278994477192940843207042535379780702841268263028"
                       +
"59486033998465467188646855777933154987304015680716"
                       +
"74391647223805124273032053960564348124852668624831"
                       +
"01273341734490560148744399254916528366159159380290"
                       +
"29782321539388697349613396698017627677439533107752"
                       + "978203");
And the proof?


Sorry, an exercise for the student. :-)

I thought that finding them was the hard part, and verifying one once found
was relatively easy.  I used the probable prime test in the Java BigInteger
package.  It sounds like, from some of the list traffic, that there are
better tests.
Indeed. The commonly used one is ECPP which uses elliptic curves 
cunningly to not only prove primality, but to produce a certificate 
which can be quickly verified.

Probabilistic prime tests are just that - probable. ECPP actually proves it.

I guess I'm dumb, but how to you verify a proof of Sophie Germain primeness
with less effort than to run the tests yourself?
Running the probabalistic tests can only prove that it's composite - 
they can never prove primality.

BTW, a terminology nit - a Sophie Germain prime is one such that p and 
2p+1 are prime - I'll be that what you've given me is one such that p 
and (p-1)/2 are prime, right?

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]