[13953] in Cypherpunks
Re: D-H key exchange - how does it work?
daemon@ATHENA.MIT.EDU (Hal)
Fri May 20 00:05:36 1994
Date: Thu, 19 May 1994 21:01:06 -0700
From: Hal <hfinney@shell.portal.com>
To: cypherpunks@toad.com
The problem with "strong" primes, primes for which (p-1)/2 is prime, is
that they are hard to find. It takes hours and hours of searching to find
a 1024 bit strong prime on a workstation. Granted, you don't need to change
very often perhaps, but some people would like to change every day. They
may need a dedicated prime-searching machine to do that.
(The best way I know to find strong primes is to find a prime q and then
check 2q+1 for primality. Finding 1024 bit primes takes a long time, and
the chances that 2q+1 is prime is very low.)
It's much easier to find a "strongish" prime, one for which (p-1)/k is
prime, where k is on the order of 100 or so. Take your prime q in the above
and try kq+1 for k=2,4,6,.... This only takes a few minutes after you find
q.
The question is, how good are strongish primes? What fraction of elements
of the group will have short periods, given that p-1 has a pretty small
number of prime factors?
Also, given a strong or strongish prime, are the chances that
g^x has a small period good enough that it makes sense to check for that
case? Any event whose chances are smaller than your computer making a
mistake is generally not worth checking for.
Hal
