17 Dec
2003
17 Dec
'03
11:17 p.m.
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