# The way to calculate $r$ from $c=r^t\mod{n}$ where $(c,t,n)$ is known

I want to know if there is a easy way to calculate $r$ from $c=r^t\mod{n}$ where $(c,t,n)$ is known and $t=pq$ is an RSA?

If $n=t^2$, is it more easier?

• Hint: that's a particular case of the RSA problem. If the factorization of $n$ gets known, that's easy. $n=t^2$ makes the later easier. – fgrieu Jul 5 '18 at 13:32
• …How do you find yourself in this situation where $t = pq$ and $n = t^2$? – Squeamish Ossifrage Jul 6 '18 at 0:29
• Because I want to get the random number in the paillier encryption $c=g^xr^t\mod{t^2}$, I can get $x$ from the private key, how can I get $r$ from $c/g^x = r^t\mod{t^2}$? – Felix LL Jul 8 '18 at 8:36

## 1 Answer

If $n$ is prime, then it is easy; we have

$$r = c^{t^{-1} \bmod n-1} \bmod n$$

If $n$ is a composite of known factorization, then it is still easy; one approach would be to have:

$$r = c^{t^{-1} \bmod \phi(n)} \bmod n$$

where $\phi(n)$ is the totient function. An equivalent approach would be to solve it for all the prime power factors of $n$, and then use the Chinese Remainder Theorem to reconstruct $r$

If $n$ is a composite of unknown factorization, well, it's believed to be hard. This is actually the RSA problem

• If $t=pq$ and $n=t^2$, is it easy? Thank you! – Felix LL Jul 5 '18 at 13:44
• @Felix LL: yes, that's easy, once $p$ and $q$ are known. Most often $r=c^{t^{-1} \bmod\phi(n)}\bmod n$ works, just be sure to compute the Euler totient $\phi(n)$ correctly. There are a corner cases, though: 1) $\min(p,q)$ might divide $\max(p,q)-1$, and then $t^{-1} \bmod \phi(n)$ will be undefined; 2) $c$ might be a multiple of $p$ or $q$ (including zero) [and that can combine with 1) or with $p=q$]. Solving modulo $p$, then modulo the highest power of $p$ in the factorisation of $n$, then if $p\ne q$ solving similarly modulo $q^2$ then using the CRT, will rigorously find all the solutions. – fgrieu Jul 5 '18 at 16:47