2
$\begingroup$

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$?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.