[1652] in cryptography@c2.net mail archive
Re: Speeding up DH
daemon@ATHENA.MIT.EDU (Phil Karn)
Fri Sep 26 23:18:53 1997
Date: Fri, 26 Sep 1997 17:43:18 -0700 (PDT)
From: Phil Karn <karn@qualcomm.com>
To: colin@nyx.net
CC: frantz@netcom.com, cryptography@c2.net, stewarts@ix.netcom.com
In-reply-to: <199709230624.AAA16242@nyx10.nyx.net> (message from Colin Plumb
on Tue, 23 Sep 1997 00:24:34 -0600 (MDT))
>Theoretically, too. Actually, it's 1/ln(2^n) and 1/ln(2^n)^2.
Which is not *too* different from 1/n and 1/(n^2). :-)
>> 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.
>Better, you only need to represent p of the form 6*x+1.
Is that right? If both p and (p-1)/2 must be odd, then that means the
low order bits of p must both be 1. That implies p's of the form 4*x+3.
Perhaps you were also trying to impose the simultaneous constraint
that the generator be 2? I don't remember offhand the rule for this...
Phil
