By Euler's theorem, if $\gcd(e,n) = 1$, then $e^{\varphi(n)} \equiv 1 \pmod n$. But why does RSA need to make sure that $\gcd(e,\varphi(n)) = 1$?


You want to be able to encrypt a message and decrypt it, that is translated to:

$m^{ed} \equiv m^1 \equiv m \pmod n$

But why? Since $ed \equiv 1 \pmod{\varphi(n)}$

If $\gcd(e,d) \neq 1$ then $e$ and $d$ are not coprime then $ed \not \equiv 1 \pmod{\varphi(n)}$. So $e$ must be coprime with $\varphi(n)$ to have a modular multiplicative inverse.

Also $\gcd(e,n)=1$, since the public key is presented as $(e,n)$. Then you trivially can compute a factor of $n$ is $e$ is not coprime.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.