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]
