# RSA: How to compute the number of possible plaintexts if $e$ is not coprime to $\varphi(n)$?

I'm studying for an exam next week, and there are two questions that me and my friend don't understand:

Question 1:
Let $p,q$ be big prime numbers and $n=pq$.
Let $e$ be a number between $1$ and $\varphi(n)$ such that $e\mid(p-1)$, $e\mid(q-1)$.
For a plaintext $M$, the ciphertext is $C=M^e \bmod n$.

How many different $M$s will be ciphered to the same $C$?
Edit: what is the maximum number of messages $M$ that will yield to the same $C$?
Why is the answer $e^2$?

Question 2:
Let $p,q$ be big prime numbers and $n=pq$.
Let $e$ be a number between $1$ and $\varphi(n)$ such that $\gcd(e,p-1)=a > 1$ and $\gcd(e,q-1)=1$.
For a plaintext $M$, the ciphertext is $C=M^e \bmod n$.

How may different $M$s will be ciphered to the same $C$?
Why is the answer $a$?

• You might want to clarify which set $M$ is chosen from. For example, if you allow $\gcd(M,n)\neq1$, a counterexample to the first question's claimed answer is given by $n=15$, $e=2$, $M=6$. – yyyyyyy Feb 7 '17 at 13:49
• Fixed the questions, for C=4, the following M yield to the same C: 13, 8,7,2 – CSE371 Feb 7 '17 at 14:05
• Since you're learning for an exam, the answers for both those questions is based on the number of roots or the order of subgroups (use Lagrange's theorem or the fundamental theorem of algebra), combined with the Chinese Remainder Theorem to assemble solutions mod $n$. – tylo Feb 7 '17 at 14:44

Both questions can be answered using the same kind of argument.

First, observe that in both cases we are really only interested in the number of $e$th roots of unity in $\mathbb Z/n$: Any $e$th root of unity can be multiplied to some $M$ without changing the value of $M^e\bmod n$, and two different $M$ with equal $M^e\bmod n$ differ by an $e$th root of unity. Thus we restrict our attention to the case $M=1$.

For succinctness, I will sometimes write only root for "$e$th root of unity".

The Chinese remainder theorem gives an isomorphism of rings $$\pi\colon\; \mathbb Z/n \cong \mathbb Z/p \times \mathbb Z/q \text.$$

The image of $x^e\bmod n$ under $\varphi$ is $(x^e\bmod p,x^e\bmod q)$. Some element $x\in\mathbb Z/n$ is a root if and only if both components of $\varphi(x)$ are roots in $\mathbb Z/p$ and $\mathbb Z/q$. In other words: Each root in $\mathbb Z/n$ "consists" of roots in $\mathbb Z/p$ and $\mathbb Z/q$, and vice-versa. Thus, if $\mathbb Z/p$ has $a$ roots and $\mathbb Z/q$ has $b$, the ring $\mathbb Z/n$ has $ab$ roots.

Now note that the order of the cyclic group $(\mathbb Z/p)^\ast$ is $p-1$, thus if $e$ divides $p-1$, there must be an element $r$ of multiplicative order $e$ in $\mathbb Z/p$. Its powers $r^1,r^2,\dots,r^{e-1}$ are nontrivial $e$th roots of unity in $\mathbb Z/p$, thus (including $1$) there are $e$ roots in $\mathbb Z/p$. There cannot be more than $e$ roots since $\mathbb Z/p$ is a field. Of course, the same holds for $q$.

Armed with that knowledge, let's tackle question 1: If $e$ divides both $p-1$ and $q-1$, there must exist $e$ different roots in both $\mathbb Z/p$ and $\mathbb Z/q$. Thus, by the above, there are $e^2$ different $e$th roots of unity in $\mathbb Z/n$.

As to question 2: Since $(\mathbb Z/q)^\ast$ has order $q-1$ and $\gcd(e,q-1)=1$, the map $x\mapsto x^e\bmod q$ is a permutation on $\mathbb Z/q$. In particular, there are no nontrivial $e$th roots of unity in $\mathbb Z/q$. Concerning $\mathbb Z/p$, note that the map $x\mapsto x^{e/a}\bmod p$ is a permutation since $e/a$ is coprime to $p-1$. Thus, $1=x^e=(x^a)^{e/a}$ in $\mathbb Z/p$ if and only if $x^a=1$. As $a\mid p-1$, we can apply the above results (with $a$ in place of $e$) to conclude that $\mathbb Z/p$ has $a$ roots, thus $\mathbb Z/n$ has $a\cdot 1=a$.