From: Xcott Craver <caj@math.niu.edu>
Date: Thu, 28 May 1998 12:40:04 -0700 (PDT)
To: Luis Saiz <LSaiz@atos-ods.com>
Subject: Re: The exponent of the RSA public key must be odd.??
In-Reply-To: <356D88D7.1D480241@atos-ods.com>
Message-ID: <Pine.SUN.3.91.980528142154.15208A-100000@baker>
MIME-Version: 1.0
Content-Type: text/plain


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"]