Quadratic residue and integer factoring

Question

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?

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.