On Thu, 16 Nov 1995, Andy Brown wrote:
Just for anyone interested, I 'found' a suspected 4096 strong prime (p and (p-1)/2 are prime) for use with Diffie-Hellman, generator of 2. As a matter of interest, how long did it take you to generate this, and with what hardware? I left a 120Mhz Pentium searching for 15 hours overnight without any success (it managed to eliminate 10 candidate primes as not strong in that time).
Well, I left it running for about 50 hours over last weekend without a hit. Then I restarted it on Monday night and got a hit in about 12 hours :-). (I thought it has finished sooner but I looked again at the 'script(1)' output and it did take 12 hours). It is sort of hard to tell how longs things would take, due to the hit or miss nature of this kind of search for primes. This is on a SGI with a 200mhz R4400 which is about the same speed as a 120mhz pentium when using my maths libraries. I'm doing the 'pick' an odd random number 'p', sieve p and (p-1)/2 over the first 2000 primes, adding in steps until a number passes the sieve. For a generator of 2, p mod 24 == 11 should be true. When it passes, then do Miller-Rabin tests on P and (P-1/2) enough times to be happy that the number is probably a prime :-). I believe that there are improvement that I can put in there for the initial search for candidate primes The actuall numbers for the search are as follows, 1057 numbers passed the 'strong prime sieve'. 7 numbers passed the prime test 1 number passed both the prime and strong prime test. I suspect the ratio of 132 cadidates for 'strong' prime testing for each 'prime' could be brought down quite a bit but since I only need strong primes for DH parameters, I probably will not spend the time on improving my initial sieve right now. eric PS, I just 'found' another 2048 bit strong prime last friday night, 2929 numbers passed the 'strong prime sieve'. 29 numbers passed the prime test (101 candidates per hit) 1 number passed both the prime and strong prime test, 4h12m run time. -- Eric Young | Signature removed since it was generating AARNet: eay@mincom.oz.au | more followups than the message contents :-)