I often read that deciding whether or not a number $r$ is a quadratic residue modulo $n$ is an interesting (and hard) problem from number theory (especially if $n$ is not prime).

I am looking at the following special case of this problem: Let $p$ and $q$ be two different prime numbers and $n:=pq$. Given $r$ between $1$ and $n$. Decide if there exists an $x\in\mathbb{Z}/n\mathbb{Z}$ such that $x^2\equiv r\pmod{n}$.

My question is: The functional version of this problem i.e. "Find such an $x$ as above" yields an randomized algorithm for integer factoring. So it is very interesting for practical reasons like "breaking RSA". Is there any such result for the decision version of this problem? If not, what are typical problems that let us think that deciding quadratic residuosity it is a hard problem?

And furthermore, is the special case I'm looking at really a special case? Or can I solve the general case with an arbitrary $n$ with an oracle for the decision problem above?

  • $\begingroup$ See the Wikipedia article on the Quadratic residuosity problem. There isn't much, but it is listed as a separate computational hardness assumption than the factoring problem and others. And though it's not known to let us factor $n$, it lets us say whether $n$ is a product of $2$ or $3$ primes. (Also there are cases where it's easy to answer No; in fact that's the case for half of all such $r$; what's hard is distinguishing in the other half the Yes instances from the No instances.) $\endgroup$ Commented Apr 15, 2019 at 23:34

1 Answer 1


Tibor Jager and Jörg Schwenk show in The Generic Hardness of Subset Membership Problems under the Factoring Assumption that factoring reduces to distinguishing quadratic residues from numbers with Jacobi symbol 1, for generic ring algorithms. These are algorithms whose only "API" to integers are ring operations (addition, multiplication, subtraction, division), equality comparisons and generating a random element. They also show that the Jacobi symbol, which can be efficiently computed in polynomial time, has no efficient generic ring algorithm. So their result doesn't answer your question, other than implying that the answer isn't known.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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