Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 4 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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