Is there an algorithm to check whether an integer $x$ is a square modulo $n$, where $n$ is an integer whose factorization we do not know? Is the Jacobi symbol helpful?
What about higher powers, e.g., testing whether $x$ is a $k$th power modulo $n$?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Recognizing squares
No. As far as we know, there is no efficient algorithm to tell whether $x$ is a square modulo $n$, if the factorization of $n$ is not known.
This is the quadratic residuosity problem; see Wikipedia for an overview. The conjecture is that the quadratic residuosity problem is as hard as factoring (i.e., the best algorithm is to first factor $n$). In fact, some cryptosystems have been built whose security rests on this assumption.
The best we can do is to use the Jacobi symbol. If the Jacobi symbol $\left(\frac{x}{n}\right)$ is $-1$, then $x$ is certainly not a square modulo $n$. However, if $\left(\frac{x}{n}\right)=+1$, then $x$ might or might not be a square. In particular, if $n$ is the product of $k$ large, distinct primes, then about $1/2^k$ of all numbers modulo $n$ are squares; about $1/2$ have Jacobi symbol $+1$; so about $1/2^{k-1}$ of all numbers with Jacobi symbol $+1$ are squares, and the remaining are non-squares. Thus, the Jacobi symbol is not enough to determine whether $x$ is a square modulo $n$.
When $n$ has known factorization
If the factorization of $n$ is known, then you can easily determine whether $x$ is a square modulo $n$ or not by using the Chinese remainder theorem. Similarly for higher powers; again, use the Chinese remainder theorem; then check whether $x^{(p^e-p^{e-1})/k} \equiv 1 \pmod{p^e}$, for each prime $p^e$ dividing $n$.
(You might also like the following post, which discusses not only how to detect whether it is a $k$th power but whether you can compute the $k$th root, when working modulo a prime $p$: https://crypto.stackexchange.com/q/6518/351. If the factorization of $n$ is known, this will determine when you can compute $k$th roots modulo $n$.)
So, in the rest of this answer, I'm assuming the factorization of $n$ is unknown, and $n$ is hard to factor.
Recognizing higher powers
What if we want to test whether $x$ is a $k$th power modulo $n$? Here things bifurcate, according to whether $k$ is relatively prime to $\varphi(n)$ or not.
If $k$ is relatively prime to $\varphi(n)$, then every number $x$ that is relatively prime to $n$ is a $k$th power modulo $n$. This follows from the fact that $(x^j)^k \equiv = x \pmod n$, where $j \equiv k^{-1} \pmod n$. (The case where $x$ is not relatively prime to $n$ is easy to handle: you compute $d=\gcd(x,n)$ and split the problem into one of determining whether $x$ is a $k$th power modulo $d$ and whether $x$ is a $k$th power modulo $n/d$.)
If $k$ divides $\varphi(n)$, then we are in a situation analogous to that of detecting squares. This is only case where I'm not 100% certain about the answer, and I don't know whether it has been studied or not. (I would conjecture that detecting $k$th powers modulo $n$ is probably also hard if $n$ is hard to factor, but I have no proof.)
If $k$ is not relatively prime to $\varphi(n)$ but does not divide $\varphi(n)$, let $k'= \gcd(k,\varphi(n))$. Then the question of whether $x$ is a $k$th power reduces to the question of whether $x$ is a $k'$th power, which is discussed above.
