# The modular n-th root (mod p*q)

I am interested in the solution of the following modular equation. Is the solution unique? If not, how difficult do find more than one solutions?

$$x^n \equiv a \; \bmod (p\cdot q)$$ where $p$ and $q$ are large primes.

Actually, I am investigating the question that is it possible (how difficult) to make more than one valid RSA signatures for a given message $a$ and a public key $n$ (with the private key $d$ known). Apparently signing $a$ with $d$ gives one valid signature. My question is how difficult to find another one. Thanks.

The solution is unique in the RSA setting where $d \equiv n^{-1} \pmod {\varphi(pq)}\;$ is assumed to exist, if $\gcd(a,pq)=1.\;$ But the case $\gcd(a,pq)\ne 1$ must be avoided anyway because otherwise you can factor $pq\;$ and your specific RSA system is broken (in practice with large primes this is very unlikely, and I do not know if in actual implementations this situation is checked).
By Euler's theorem the unique solution is $$x \equiv a^{d} \pmod {pq}\equiv a^{n^{−1}\pmod {\varphi(pq))}} \pmod {pq}$$
• I think gcd$(n, \phi(pq))$ is a sufficient condition of unique solution. Sep 19 '14 at 16:30