[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