1
$\begingroup$

I understand that if $e\in{\mathbf{Z^*_{\phi(N)}}}$ then $\gcd(e,\phi(N))=1$ and if $e\not\in{\mathbf{Z^*_{\phi(N)}}}$ than $\gcd(e,\phi(N))\neq{}1$.

But I couldn't figure out why this implies bijection of $f(x)=x^e$.

I also tried to see examples but that didn't help me to explain the phenomenon.

$\endgroup$
  • 1
    $\begingroup$ Could you also post your failed examples? Also, a dupe question Proving RSA is a permutation. $\endgroup$ – kelalaka Jun 16 '20 at 8:55
  • 1
    $\begingroup$ Note that, learning from your errors (LWE) is more valuable for development. That is why I've asked your failed ways. $\endgroup$ – kelalaka Jun 16 '20 at 9:28
  • 1
    $\begingroup$ Actually, it's not true. Counterexample, $\mathbf{N}=8$, $e=3$... $\endgroup$ – poncho Jun 16 '20 at 10:22
  • $\begingroup$ @poncho The OP tagged RSA. $8$ doesn't form RSA or multi-prime RSA. $\endgroup$ – kelalaka Jun 16 '20 at 10:35
  • $\begingroup$ If the linked answer satisfies you we can close this question and before that make sure that $N$ is RSA modulus. If you are not talking only RSA then poncho's hint also valid for you. $\endgroup$ – kelalaka Jun 16 '20 at 13:09
1
$\begingroup$

The correct form is: The integer $a \mod Z_n$ has multiplicative inverse iff $gcd(n,a)=1$

Here, you are working on exponents, so you must consider the modulo as $\phi(n)$ not $n$.

Therefore, here you can find the inverse of $e$ iff $gcd(e, \phi(e))=1$. This guarantees that you be able to find the inverse of $e$ using extended Euclidean algorithm.

$\endgroup$

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.