# Detect if an element is in an orbit.

Suppose $$n = pq$$ is a product of two distinct primes. We also know that integer $$r$$ divides $$\varphi(n) = (p-1)(q-1)$$ and $$r^2$$ doesn't divide it. Fix element $$x$$ of $$\mathbb{Z}_{n}$$. Can we tell easily whether $$x$$ is in the set $$\{y^r : y \in \mathbb{Z}_{n}\}$$? $$r$$ is small, but $$n$$ is big, and thus we don't know $$p$$, $$q$$ and $$\phi(n)$$.

• So you are assuming that you don't know what $p$ and $q$ are? – Morgan Rodgers Apr 23 at 22:52
• Yes, I don't know both $p$ and $q$. – enedil Apr 23 at 22:54
• Sounds like a difficult problem. You are trying to determine if $x$ is a $r$th-power residue modulo $n$. Most of the techniques I have seen for this require $n$ to have a primitive root (not the case when $n$ is a product of odd primes). – Morgan Rodgers Apr 23 at 22:55
• You would maybe be better of trying to find $p$ and $q$, using the knowledge that exactly one of $p$,$q$ is congruent to $1 \bmod{r}$ but not $\bmod{r^{2}}$. – Morgan Rodgers Apr 23 at 22:57
• See here for some ideas related to your original problem (though they require you to find $p$ and $q$): en.wikipedia.org/wiki/Power_residue_symbol – Morgan Rodgers Apr 23 at 22:59