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