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

-