In the case of Euler's phi function, we know from the Euler generalization of Fermat's little theorem that $M^{\phi(n)} \equiv 1$ mod n. However a lot of modern RSA implementations use LCM ($\lambda(p-1,q-1)$), where $pq = n$, instead of $\phi(n)$. How do we know that any $d$ that is coprime with LCM(p-1,q-1) will produce $m^{ed} \equiv m$ mod n?
Asked
Active
Viewed 262 times
0
-
1What's $\lambda$? Do you understand that $\phi(pq)=(p-1)(q-1)$ if $p$ and $q$ are distinct primes? – J. W. Tanner Apr 15 '21 at 01:57
-
$\lamba$ is just least common multiple here. I understand the $\phi$ bit, but I dont understand why it also applies to LCM. I understand that it might have something to do with the fact that $\lambda(p-1,q-1)$ divides $(p-1)(q-1)$, but I'm not sure where to go from there. – wasianpower Apr 15 '21 at 02:00
-
2If $M^\lambda \equiv 1\pmod p$ and $\pmod q$, then $M^\lambda \equiv 1 \pmod {pq }$ by the Chinese remainder theorem – J. W. Tanner Apr 15 '21 at 02:10
-
2If $M^{p-1}\equiv 1\pmod p$, then $M^\lambda\equiv 1\pmod p$ – J. W. Tanner Apr 15 '21 at 02:17
-
1See also the Carmichael function. – Troposphere Apr 15 '21 at 02:21
-
Might help you; More than one private key for RSA – kelalaka Apr 19 '21 at 23:23