# Which divisors produce unique moduli? (for RSA encryption)

Sorry if this question is confusing, I'm still confused by the whole thing.

I'm trying to understand how RSA encryption works, but I'm having trouble with the modulus part. For RSA to work, $c=m^e \bmod n$ must give an unique $c$ as long as $0<m<n$. I'm trying to find a pattern for the combinations of $e$ and $n$ that produce an unique $c$ for each $m$. I'm having trouble find any patterns.

When I tried $e=3$, $n=2,3,5,6,10,11,15,17$ all produce unique $c$'s as long as $0<m<n$. I don't see any patterns in that list.

• $e$ must be relatively prime to $\phi(n)$, which is the number of integers prime to and not exceeding $n$. Jan 2 '14 at 21:58
• But $ϕ(4)=2$ is relatively prime to $e=3$, but that doesn't produce unique $c$'s. Jan 2 '14 at 22:12
• Actually, if you only require uniqueness for $0<m<n$, $e=3$ does produce unique $c$'s for $n=4$ :-) That's why it's usually required to have the uniqueness for $0\leq m<n$, zero included. Jan 2 '14 at 23:23
• For $n=4$, my moduli are $1,0,3,0,1,0,3,0...$. If $m=2$ or $m=4$, the moduli are both zero. Am I doing something wrong? Jan 2 '14 at 23:48
• I think one generally asks for $m$ and $n$ to be relatively prime. Jan 3 '14 at 0:41

There are two conditions, one on $n$ and one on $e$ in relation to $n$:

• $n$ must be square-free (= not divisible by square of any prime). If $n$ was divisible by $p^2$ for some prime $p$, then $(n/p)^e = n\left(\frac{n}{p^2}\right)(n/p)^{e-2}$ would be a obvious multiple of $n$ for $e\geq 2$, which means $(n/p)$ would clash with $0$ modulo $n$ when raised to $e$-th power. This condition is usually guaranteed in the RSA scheme by making $n$ a product of two distinct primes.
• $e$ must be coprime to $\phi(n)$: $\gcd(e,\phi(n))=1$.

RSA is motivated by how computationally difficult it is to factor large numbers. I was under the impression that $n$ had to be a product of two unique prime numbers (in any sort of practical application these would be very large primes). If we set this restriction for $n$, then we can produce a unique $c$ for any $e$ such that $\gcd(\phi(n),e)=1$.

An informal proof that the algorithm works for $n=pq$, where $p,q$ are prime, can be found on page 108 of Tom Judson's open source intro algebra book: abstract.pugetsound.edu

• I'm not convinced that this works, if $e$ has a common factor with $(p-1)(q-1)$. Jan 3 '14 at 0:43
• @GerryMyerson you are absolutely correct. I overlooked this basic but very important condition. I will change my answer accordingly.
– KcH
Jan 3 '14 at 5:36

As was said above, RSA ensures this by taking $n = pq$ for $p,q$ two distinct (large) primes, and $e$ coprime with $\phi(n) = (p-1)(q-1)$. Then the encryption map $\mathsf{enc}: m \mapsto m^e \bmod n$ is a permutation of $\{0,\dots,n-1\}$.

To show this, since the set is finite we need only show either injectivity or surjectivity, we will show surjectivity. Let $c \in \{0,\dots,n-1\}$, we claim that $c = \mathsf{enc}(c^d \bmod n)$, where $d = e^{-1} \bmod{\phi(n)}$. This means that $c = c^{de} \bmod n$. Now, we have $de = 1+k\phi(n) = 1+k(p-1)(q-1)$, so we get $$c^{de} = c^{1+k(p-1)(q-1)} = c\times (c^{p-1})^{k(q-1)} \mod p,$$ and Fermat says that if $c$ is not a multiple of $p$, we have $c^{p-1} = 1 \bmod p$ so we obtain $c^{de} = c \bmod p$. If $c$ is a multiple of $p$ we have $c = 0 \bmod p$ and so $c^{de} = 0 = c \bmod p$ as well. Apply the same argument mod $q$, and the Chinese theorem concludes that $c^{de} = c \bmod n$.

(The proof is somewhat simpler if you assume that $m$ and $n$ are coprime as Gerry Myerson indicated.)