🚀 go-pugleaf

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