How to make RSA function injective I'm trying to make the RSA function $ F(c) = m^e \mod n $ injective (ie, always generates a unique value for $ c $ / don't repeat values in set $ C $). Through some research, I've found this is possible through a specific value of $ e $, but I can't find anywhere the exact value.
So... does anyone know which value $ e $ needs to be to $ c = m^e \mod n $ be injective?
 A: As many others have mentioned, it suffices to take $e$ with $1 < e < \phi(n)$ and $\gcd(e,\phi(n)) = 1$.
Let's remember why this works. At the end of the day we'd like to be able to decrypt the message again, and as it seems you know how the RSA algorithm works, you know that the decryption scheme is essentially the same as the encryption scheme: you find a suitable number $d$, depending on $e$ and $n$ and want to find $m$ as
$$c^d \mod n.$$
That is, we want to choose $d$ such that $m^{de} \equiv m \mod n$ or $m^{de-1} \equiv 1 \mod n$. It suffices to check that this congruence holds $\mod p$ and $\mod q$, where $n = pq$. At this point, you should recall Fermat's little theorem which says that
$$m^{p-1} \equiv 1 \mod p$$
for any prime $p$ not dividing $m$ (the latter assumption meaning that some cases should be checked separately below). Therefore, it would be neat if $de -1$ were a multiple of both $p-1$ and $q-1$, i.e. that $de-1 = k(p-1)(q-1)$ for some $k$. Now $\phi(n) = \phi(pq) = (p-1)(q-1)$, so it will suffice to take $e$ as in the first line of this answer: the assumption that $\gcd(e,\phi(n)) = 1$ ensures that $e$ has a multiplicative inverse $d$ modulo $\phi(n)$, i.e. a number $d$ satisfying $de \equiv 1 \mod \phi(n)$, which is exactly what we need.
A: You have to choose $e$ to be coprime with $\phi{}(N)$. It is a requirement in RSA.
For example a prime number nearly always work ($e = 17$ and $e = 65537$ are used a lot).
