> Fine. Can you point me to a paper or book where this algorithm is
> described (such as the publication that earned it its name)?
H Williams and B Schmid, Some Remarks Concerning the MIT
Public Key Crypto Systems, BIT, 1979, Vol 19, pp 525-38
In brief the algorithm is as described below. This is itaken
from the source code comments of the stuff I'm going to send
to the people who want it when it's in a fit state for human
consumption.
/*
The Williams-Schmid method for generating strong primes
i.e. primes of the form p = 2q+1 where q is also prime uses
the following algorithm:
1. Select two randomly chosen primes, p1 and p2, of
about the same length.
2. Find x such that x*p2 = -1 mod p1
3. Generate a set of numbers { (Si, Ti) } where
Si = 2*p1*p2*i + 2*p2*x + 1
Ti = 2*S + 1
We can pre-compute the expressions
Y = 2*p1*p2
and
Z = 2*p2*x + 1
before we start iterating over the set.
There is no magic number for the size of the set,
but the authors of the paper suggest that i runs
through the domain ( i = 1,,2,3...,L) where
L = 1.5(ln4p1p2)^2
4. Sieve the numbers by sequentially testing each pair
for being composite by using the 168 primes smaller than
1000. This test weeds out about 99% of candidate pairs.
Empirically, I have got slightly better results ( about
99.2% of pairs weeded out) using the first 2048 primes. The
slight difference in referrals to the fifth stage does
increase the speed, albeit only very slightly. To build the
code with the big sieve use the flag -DBIG_SIEVE in the
Makefile.
5. The final step is to check the two congruences
3^(Si - 1) = 1 mod Si
3^(Si) = 1 mod Ti
hold.
If they do then both Si and Ti are prime and are, by
construction, of the form required.
*/
Chad.
______________________________________________________________________
OpenSSL Project http://www.openssl.org
Development Mailing List [EMAIL PROTECTED]
Automated List Manager [EMAIL PROTECTED]
