# Computing the cardinality of the co-domain of specific modular exponentiations

Consider the following function:

$f: \mathbb{Z}_n \rightarrow Y,~x \mapsto x^e \bmod n$,

where $n = p \cdot q$ is an RSA modulus and $\gcd(\varphi(n),e) \neq 1$ (contrary to what's required for a public RSA exponent) with $\varphi(n) = (p-1)\cdot (q-1)$.

How can the cardinality of $Y$ be computed or estimated (in terms of $n$ and $e$)?

One way to approach this problem is to first look at the simpler problem of that cardinality of $x^e \bmod p$ where $p$ is prime, and $gcd(p-1, e)$ might not be 1.

In that case, we have two cases: $x \equiv 0 \pmod{p}$, which makes it obvious that 0 will always be a possible postimage, and $x \in \mathbb{Z}^*/p$; in this second case, that group is isomorphic to the simpler group $\mathbb{Z}/{p-1}$; considering that simpler group, it should be obvious that there are $\frac{p-1}{gcd( p-1, e)}$ possible postimages. Combining the two gives us $1 + \frac{p-1}{gcd( p-1, e)}$ total postimages.

Now, going back to your original question, $p$ and $q$ are relatively prime, and so by the Chinese Remainder Theorem, any pair of inputs $x \bmod p$ and $x \bmod q$ are possible. In addition, a postimage $x^e \bmod n$ is possible iff the corresponding postimages $x^e \bmod p$ and $x^e \bmod q$ are both possible.

The upshot of this is that the total number of possible postimages is the product of the number of postimages mod p times the number of postimages mod q. Or, in other words,

$$|Y| = \lgroup 1 + \frac{p-1}{gcd( p-1, e)}\rgroup \cdot \lgroup 1 + \frac{q-1}{gcd( q-1, e)} \rgroup$$

We see that if $\gcd( \phi(p), e) = 1$, then $gcd(p-1,e)=1$ and $gcd(q-1,e)=1$, and this formula simplifies to $|Y| = pq = n$

I know that you asked for a function depending on $n$ and $e$, however since it is believed to be computationally infeasible to compute $gcd( \phi(n), e )$, coming up with even a formula to estimate $|Y|$ looks impractical.