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)$.

  • $\begingroup$ So you are assuming that you don't know what $p$ and $q$ are? $\endgroup$ – Morgan Rodgers Apr 23 at 22:52
  • $\begingroup$ Yes, I don't know both $p$ and $q$. $\endgroup$ – enedil Apr 23 at 22:54
  • 1
    $\begingroup$ 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). $\endgroup$ – Morgan Rodgers Apr 23 at 22:55
  • $\begingroup$ 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}}$. $\endgroup$ – Morgan Rodgers Apr 23 at 22:57
  • 1
    $\begingroup$ 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 $\endgroup$ – Morgan Rodgers Apr 23 at 22:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.