Talk:Quadratic residue

From Wikipedia, the free encyclopedia

[edit] Vagueness

From the article: "The law of quadratic reciprocity says something about quadratic residues and primes." Surely we can do better? 02:12, 19 October 2005 (UTC)

[edit] NP-Hardness ??

I doubt, that this paragraph

On the other hand, if we want to know if there is a solution for x less than some given limit c, this problem is NP-complete; ...

is true. I think the author wanted to mention, that the related decision-problem is in NP, but not that it is NP-hard. As far as I can see, factoring directly solves the decision problem mentioned here, thus factoring would solve an NP-hard problem and be NP-hard itself. It is open, whether factoring is NP-hard.

From Integer_factorization:

It is suspected to be outside of all three of the complexity classes P, NP-Complete, and co-NP-Complete. If it could be proved that it is in either NP-Complete or co-NP-Complete, that would imply NP = co-NP. That would be a very surprising result, and therefore integer factorization is widely suspected to be outside both of those classes.

Please comment, especially if I am wrong. --GrGr 11:02, 13 June 2006 (UTC)

You are wrong. The keyword is less than some given limit: IOW, the set of all triples such that is NP-complete. Factoring does not help here, the problem remains NP-complete even if the factorization of n is known. -- EJ 18:49, 14 June 2006 (UTC)

Right, I was wrong. I didn't notice, that the reference to Garey & Johnson refers to this section. In the mean time, I thought, that a simple many-one reduction to the decisional version of factoring doesn't help, because you have only one call to the oracle, and thus need a polynomial time Turing reduction. But you are right, as G&J state, even if the factorization of n is given with the input instance, the problem remains NP-complete (although currently I still don't understand it, I will look for Manders and Adleman's paper). --GrGr 06:27, 16 June 2006 (UTC)

Now I scanned through the proof, I recognize, where my intuition was wrong. I considered n to be a composite of few primes like a Blum integer. The NP-hardness result is derived from a reduction from 3-SAT which actually requires n to be a product of distinct primes for 3-SAT instances with variables. So, if you have two possible roots modulo each prime, you get an exponential amount of possible roots modulo n (at least, that's my new intuition). --GrGr 09:10, 16 June 2006 (UTC)

Indeed, that's my intuition too. -- EJ 17:26, 16 June 2006 (UTC)