[1572] in cryptography@c2.net mail archive
Re: Speeding up DH
daemon@ATHENA.MIT.EDU (Phil Karn)
Mon Sep 22 22:21:40 1997
Date: Sat, 20 Sep 1997 06:08:38 -0700 (PDT)
From: Phil Karn <karn@qualcomm.com>
To: frantz@netcom.com
CC: colin@nyx.net, cryptography@c2.net, stewarts@ix.netcom.com
In-reply-to: <v03007837b042649b8d7c@[207.94.249.39]> (message from Bill Frantz
on Sun, 14 Sep 1997 23:15:23 -0700)
>I used Java's java.math.BigInteger function to get a 1023 bit prime. I
>then doubled it, added one and checked the result for primality. I then
Primality checking based on Fermat's little theorem and variants is
expensive, and strong primality testing is literally "expensive
squared". (p is a "strong prime" if both it and (p-1)/2 are prime.)
So it's definitely worth sieving out candidates for which either p or
(p-1)/2 have small factors (or 2p+1, if you do it that way).
My approach was to build an "overlaid sieve window" at my random
starting point big enough to expect to hit at least one strong prime
in the window. The density of primes in the vicinity of 2^n is known
to be about 1/n, so I conjectured that the density of strong primes
would be about 1/(n^2). (Experimentally, this seems to be the case.)
For a 1024-bit strong prime, your sieve "window" should be at least a
million or two. Use a bit map to save RAM, and of course you only
need to represent odd numbers.
Using all remaining available RAM, I also built an auxiliary sieve to
generate a complete list of small primes. With this list, I walk
through the main sieve marking off any entry for which either p or
(p-1)/2 is divisible by the small prime.
I then run full-blown Fermat primality tests on the few surviving
candidates in the primary sieve. First I check p. Only if that passes
do I test (p-1)/2. As soon as I find a candidate that passes both
tests, I stop.
The importance of agressive sieving cannot be overstated. It's been a
while since I did this, but I seem to recall that by generating a list
of small prime factors up to about 5 million and rejecting candidates
divisible by these factors I only had to run the primality test on
only about 0.1% of the odd candidates in my search window. It took a
while to generate the small factors and to do the sieving, but this
effort was more than paid back by the savings in avoided Fermat
tests. So make your list of small prime factors as big as you can, up
to the point where your machine begins paging.
Phil
