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 majordomo at wasabisystems.com