0
$\begingroup$

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$)?

$\endgroup$
5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.