Path: utzoo!mnetor!uunet!lll-winken!lll-tis!ames!umd5!purdue!i.cc.purdue.edu!k.cc.purdue.edu!l.cc.purdue.edu!cik
From: cik@l.cc.purdue.edu (Herman Rubin)
Newsgroups: sci.crypt
Subject: Re: RSA Discussion and Speculation
Message-ID: <755@l.cc.purdue.edu>
Date: 18 Apr 88 11:24:59 GMT
References: <6053@watdragon.waterloo.edu> <114@cvbnet2.UUCP> <49480@sun.uucp> <49704@sun.uucp>
Distribution: na
Organization: Purdue University Statistics Department
Lines: 27
Keywords: RSA algorithm wanted
Summary: A small observation

In article <49704@sun.uucp>, falk@sun.uucp (Ed Falk) writes:
> In article <921@rlgvax.UUCP>, dennis@rlgvax.UUCP (Dennis.Bednar) writes:
> > In article <49480@sun.uucp>, falk@sun.uucp (Ed Falk) writes:

> Apparently, there are a large number of d and e for each (p,q).  According
> to R,S,A, you choose any d such that d is relatively prime to (p-1)*(q-1).
> 
> 	gcd( d, (p-1)*(q-1) ) = 1

> e is simply the "multiplicitive inverse" of e, mod (p-1)*(q-1).
> 
> 	(e*d) mod (p-1)*(q-1) = 1

What Ed says is correct but slightly misleading.  Instead of using 

	(p-1)*(q-1)

the use of lcm( p-1, q-1) is more enlightening, as two values of d or
e which differ by multiples of this number are equivalent.  This is 
why the example given with p=3, q=7 is not very revealing.  The only
values for d and e in this case are 1 and 5.  There is even a discussion
in the literature of choosing p and q so that there are few factors in
common between p-1 and q-1; taking p = 2r+1, r prime, is one way to do
this.  It is important that p and q are difficult to find.
-- 
Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907
Phone: (317)494-6054
hrubin@l.cc.purdue.edu (ARPA or UUCP) or hrubin@purccvm.bitnet