> > I ask because I have some code (somewhere!) that implements the
> > Williams-Schmid method for creating these primes by construction.
>
> By construction? Interesting. I always thought there is no efficient
> construction process possible for prime-number generation, isn't it?
Hmmm... I don't know how _efficient_ it is, but in the tests I did on it, the
average time to create a 1024 bit strong prime (and one _guaranteed_ strong, by
construction) was 1014 seconds, as opposed to 2301 seconds for BN_generate_prime()
with "strong" set to 1. This was on a Sparc Ultra 2 running SunOS. My P2 266MHz
laptop running RH Linux 5.2 is even faster - by a factor of about 4 or 5, maybe
more.
For small primes, say, 256 bits, the BN method appears to be faster.
The drawback is that because of the way the algorithm works, the size is somewhat
variable, though this can be made better with empirical adjustments to the
seed-data. For example, after asking for 1024 bit primes, I tended to end up with
1032 bit ones. I don't know if this is a problem or not. Is it?
If anyone is interested, I'll post a description of the algorithm and my source code
and test program so you can all play with it. If you like it, you can stick it in
OpenSSL to give people a choice of methods.
However, I remember reading somewhere that because of improvements in algorithms to
find discrete logs, the need for a strong prime is not so important these days,
just so long as you have _reasonably large factors of p-1_. So, while a having a
Mersenne prime as a factor of p-1 would be pretty dumb, generally speaking, strong
primes are not as important as once thought. I may have dreamed all this, of
course.
Chad.
______________________________________________________________________
OpenSSL Project http://www.openssl.org
Development Mailing List [EMAIL PROTECTED]
Automated List Manager [EMAIL PROTECTED]
