[2778] in cryptography@c2.net mail archive
Re: The exponent of the RSA public key must be odd.??
daemon@ATHENA.MIT.EDU (Xcott Craver)
Thu May 28 15:51:03 1998
Date: Thu, 28 May 1998 14:39:43 -0500 (CDT)
From: Xcott Craver <caj@math.niu.edu>
To: Luis Saiz <LSaiz@atos-ods.com>
cc: Sunder <sunder@brainlink.com>, cypherpunks <cypherpunks@toad.com>,
"cryptography@c2.net" <cryptography@c2.net>
In-Reply-To: <356D88D7.1D480241@atos-ods.com>
On Thu, 28 May 1998, Luis Saiz wrote:
> OK, I've never realized that e and d must both be co-prime with respect to (p-1)(q-1),
> only that ed=1 mod((p-1)(q-1)), and I didn't saw the implication.
Actually, that the exponent must be odd is much more immediate:
If ed = 1 mod(p-1)(q-1), then
ed = 1 + multiple*(p-1)(q-1)
= 1 + multiple*(even #)
= 1 + even # = odd #.
If either e or d were even, this couldn't be true.
-Xcott
[This same argument, by the way, is how you prove that
e and d must both be co-prime to phi(n). Just let
C be any divisor of phi(n), and replace "even" with
"divisible by C" and "odd" with "not divisible by C"]
