Timeline for Why $f(x)=x^e$ is a bijection i.f.f $e\in{\mathbf{Z^*_{\phi(N)}}}$?
Current License: CC BY-SA 4.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 17, 2020 at 4:38 | comment | added | fgrieu♦ | As an illustration that important characteristics include square-freeness of $N$, and the set on which we consider the bijection, consider: $N=9$, $e=5$. We have $e\in\Bbb Z_{\phi(N)}^*$, yet $f(3)=f(6)$ for $f(x)=x^e\bmod N$, where $3,6\in\Bbb Z_N$ and $3,6\not\in\Bbb Z_N^*$. | |
| Jun 16, 2020 at 22:42 | comment | added | fgrieu♦ | In the question it must be meant $f(x)=x^e\bmod N$, not $f(x)=x^e$, which in general is not a bijection. This or this proves that if $e\in\Bbb Z_{\phi(N)}^*$ and $N$ is square-free, then $f$ is a bijection on $\Bbb Z_N$. That also works for a bijection on $\Bbb Z_N^*$ and the proof is simpler. For a (less usual) proof in the other direction, see this. If you don't want the square-free hypothesis, well, go ahead! | |
| Jun 16, 2020 at 20:58 | answer | added | m123 | timeline score: 1 | |
| Jun 16, 2020 at 13:09 | comment | added | kelalaka | 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. | |
| Jun 16, 2020 at 10:35 | comment | added | kelalaka | @poncho The OP tagged RSA. $8$ doesn't form RSA or multi-prime RSA. | |
| Jun 16, 2020 at 10:22 | comment | added | poncho | Actually, it's not true. Counterexample, $\mathbf{N}=8$, $e=3$... | |
| Jun 16, 2020 at 10:08 | history | edited | A. Maman | CC BY-SA 4.0 |
edited title
|
| Jun 16, 2020 at 9:42 | history | edited | AleksanderCH | CC BY-SA 4.0 |
Corrected spelling
|
| Jun 16, 2020 at 9:28 | comment | added | kelalaka | Note that, learning from your errors (LWE) is more valuable for development. That is why I've asked your failed ways. | |
| Jun 16, 2020 at 8:55 | comment | added | kelalaka | Could you also post your failed examples? Also, a dupe question Proving RSA is a permutation. | |
| Jun 16, 2020 at 8:53 | history | edited | kelalaka | CC BY-SA 4.0 |
\gcd
|
| Jun 16, 2020 at 8:32 | history | asked | A. Maman | CC BY-SA 4.0 |