Let $N$ be the product of two primes and let $P$ be the smallest prime larger than $N$.
- Let the algorithm $R(N,s)$ return $s^{1/P} \pmod{N}$.
- Let the algorithm $\widehat{R}(N,s)$ pick a random element $u\leftarrow \mathbb{Z}^*_N$ and return it.
Show that you can distinguish $R$ from $\widehat{R}$ with significant advantage; that is, show that there is an efficient (potentially probabilistic) algorithm $\mathcal{A}$ for which
$$\left|\Pr_{N,s}\left[\mathcal{A}(N, s, R(N,s) ) = 1\right] - \Pr_{N,s}\left[\mathcal{A}(N,s,\widehat{R}(N,s))=1\right]\right| \geq \frac{1}{2}$$
Note: This is a homework question, so I would like hints for how to become unstuck, not full solutions.
So far, I have tried to discover what behavior the map $\square\mapsto \square^{1/P}$ has, but with little luck. I believe the maps $\square\mapsto \square^{P}$ and $\square \mapsto \square^{1/P}$ (modulo $N$) are always permutations since $\varphi(N)$ and $P$ are necessarily coprime. This is a confusing result, because it suggests that $R(N,\cdot)$ is a permutation of $\mathbb{Z}_N^*$, which I would think would make it hard to distinguish from random.
I am also trying to determine whether $s^{1/P}$ "leaks" important information about $s$, perhaps parity or something. I believe it does, but I am not sure where.
Suggestions for where to look next?