[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Lucky primes & omlets on my face...
> > 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
[email protected]
415/329-6913
finger for PGP public key
D4 99 54 2A 98 B1 48 0C CF 95 A5 B0 6E E0 1E 1D