[1653] in cryptography@c2.net mail archive
Re: Speeding up DH
daemon@ATHENA.MIT.EDU (Colin Plumb)
Fri Sep 26 23:26:10 1997
Date: Fri, 26 Sep 1997 19:03:17 -0600 (MDT)
From: Colin Plumb <colin@nyx.net>
To: colin@nyx.net, karn@qualcomm.com
Cc: cryptography@c2.net, frantz@netcom.com, stewarts@ix.netcom.com
>> 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.
Eep, I made some pretty bad errors posting off-the-cuff like that.
(I got it right in my code, I promise! I was just relying on faulty memories
of the code.)
There is a mod 6 constraint on (p-1)/2. and thus a mod 12 constraint on
p. You've spotted the mod 4 part, derived from the fact that (p-1)/2
must be odd.
Consider the possible value of (p-1)/2 mod 3:
0 - Obviously, not prime
1 - doubling this and adding 1 gives p == 3 (mod 3), which is also not prime
2 - doubling this and adding 1 gives p == 2 (mod 3), which is possible.
Thus, (p-1)/2 == 5 (mod 6) and p == 11 (mod 12) is correct.
> Perhaps you were also trying to impose the simultaneous constraint
> that the generator be 2? I don't remember offhand the rule for this...
No, that's mod 8. p being either +/-1 or +/-3 makes for generator and
non-generator mod p. It's in my bnjacobi.c file, but I have to dash
out the door right now...
--
-Colin
