Is it possible to calculate the random factor $r$ from a encrypted message and the private key in a Paillier cryptosystem? I have already done my research and found various sources that state that it is possible but there are also a lot of them that says it is not possible to recover $r$. This Q/A on this site for example even states the formula to get it. I don't know if it is wrong or I am missing something since I was not able to make a working implementation of it.

Some friends told me it is impossible to get $r$ back since it was raised during encryption to the $n$-th power and ended up in a smaller subgroup which results in a loss of information that renders it unable to be recovered.

I asked on reddit and got told the following:

$r$ is choosen to be between 0 and $n^2$. The plaintext can be between $0$ and $n$. The Ciphertext is however also between $0$ and $n^2$. Since the plaintext is fully preserved, the same is impossible for the randomness, as this would otherwise violate the theorem that lossless compression is impossible.

I would like to know whether it is possible to calculate $r$ and how it is computed given that I have:


$C \to$ ciphertext
$P \to$ plaintext
$N \to$ public key modulo $(p\cdot q)$


Also if it is not possible for all $r$ values to be recovered I would like to know if it would be possible to recover $r$ values smaller than $m$ bits (I know that reducing $r$ bit length makes the encryption less secure)
It is strange that Wikipedia propose to choose $r\mod N^2$ while $r^N\mod N^2$ depends on $r\mod N$ only:
$$(r+tN)^N=r^N+r^{N-1}tN^2+\ldots\equiv r^N\pmod{ N^2}.$$ It means that you can recover only $r\mod N.$ In order to do it you can use the formula from the cited answer
$$r\equiv (r^N)^M\pmod{ N}, $$
where $M = N^{-1}\bmod \phi(N)$.