Talk:Quadratic residue
From Wikipedia, the free encyclopedia
 |
|||||
| Mathematics grading: | Stub Class | Importance unassessed. | Field unassessed. | ||
[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)
- 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
-
-
- 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)
- 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
-
-
-
-
- Indeed, that's my intuition too. -- EJ 17:26, 16 June 2006 (UTC)
-
-
