Ben Laurie writes: > Apologies, slightly at cross-purposes here. For a start, Sophie Germain > primes are needed for D-H (or rather, safe primes), and secondly, I was > talking about proving arbitrary primes, rather than constructing > provable primes.
Dan Bernstein has lots of good information on the state of the art in general primality (and compositeness) proving. http://cr.yp.to/primetests.html points to his recent survey paper and has a table of the various algorithms. Interestingly there are considerable tradeoffs between proving time and verification time. There are some methods that create "instant" proofs but then take a long time to verify. http://cr.yp.to/ntheory.html has some of Dan's own work, including an algorithm which creates a certificate in time quadratic in length, with verification costing time proportional to the 4th power of the length. He suggests that at this point the best practical algorithm is based on elliptic curves, which is conjectured to have running time proportional to the 4th power of length for finding proofs and to the 3rd power for verifying them. I don't know what the actual numbers are for prime sizes of interest (presumably 1K-8K bits or so). References are available from his papers. Several programs to implement ECPP can be found from http://primes.utm.edu/links/programs/seeking_large_primes/. I don't know about source code however. It might be interesting to run these over some of the Oakley primes and publish the certs - I vaguely recall seeing something like that in an RFC. Hal --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
