February 13, 2023
RSA {2} Why RSA must make sure that gcd(e,φ(n))=1
Why RSA must make sure that $gcd(e,φ(n))=1$ instead of $gcd(e,n)=1$?
By Euler’s theorem, if $gcd(e,n)=1$, then $eφ(n)≡1\pmod n$. But why does RSA need to make sure that $gcd(e,φ(n))=1$?
encode:
$$ m^{ed} \equiv m^1 \equiv m\pmod n $$But why does this word? Since $ed \equiv 1 \pmod {\varphi(n)}$ if $gcd (e, d)\not= 1$ then $e$ and $d$ are not coprime ,then $ed \not= 1 \pmod {\varphi (n)}$.So $e$ must be coprime with $\varphi(n)$ to have a modular multiplicative inverse.(模反元素) Also $gcd(e, n) \equiv 1$, since the public key is presented as $(e, n)$. Then you trivially can compute a factor of $n$ if $e$ is not coprime.