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.

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ Could you also post your failed examples? Also, a dupe question Proving RSA is a permutation. $\endgroup$
    – kelalaka
    Commented Jun 16, 2020 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
    Commented Jun 16, 2020 at 9:28
  • 1
    $\begingroup$ Actually, it's not true. Counterexample, $\mathbf{N}=8$, $e=3$... $\endgroup$
    – poncho
    Commented Jun 16, 2020 at 10:22
  • $\begingroup$ @poncho The OP tagged RSA. $8$ doesn't form RSA or multi-prime RSA. $\endgroup$
    – kelalaka
    Commented Jun 16, 2020 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
    Commented Jun 16, 2020 at 13:09

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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