# Quadratic residue and integer factoring

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?

• 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.) – ShreevatsaR Apr 15 '19 at 23:34