From: chen@intuit.com (Mark Chen)
Date: Fri, 3 Feb 95 13:58:56 PST
To: hfinney@shell.portal.com (Hal)
Subject: Re: Lucky primes & omlets on my face...
In-Reply-To: <199502020213.SAA17094@jobe.shell.portal.com>
Message-ID: <9502032157.AA04050@doom.intuit.com>
MIME-Version: 1.0
Content-Type: text/plain



> > Recall:  x^p = x mod p therefore, x^(p-1) = 1 mod p. So what we need is:
> > (x^e)^d = x^ed = x^(p-1)*i+1 = x mod p.  
> 
> This would only be true for prime p, but with RSA we are dealing with
> composite moduli.  What we want is ed=1 mod phi(n), where
> phi(n)=(p-1)(q-1).  (Actually you want to use (p-1)(q-1)/gcd((p-1),(q-1)).
> I forget what that is called.)

"Least common multiple," or LAMBDA(n).


--
Mark Chen 
chen@intuit.com
415/329-6913
finger for PGP public key
D4 99 54 2A 98 B1 48 0C  CF 95 A5 B0 6E E0 1E 1D