Talk:Quadratic residue

From Wikipedia, the free encyclopedia

Contents

[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 \langle q,n,c\rangle such that \exists x\le c\,(x^2\equiv q\pmod n) 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 \{\langle n,c\rangle \|\ \exist p<c: p\mbox{ divides } n \} 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 \Theta(\ell^3) distinct primes for 3-SAT instances with \ell 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)

[edit] even characteristic vs char = 2

What's the point in writing "field of even characteristic" instead of "characteristic 2" ? AFAIK, the characteristic of a field is always prime, except if its 0, which is even, but for which the statement of every element being a square is wrong: char(Q)=0 i.e. even, but not every element of Q is a square. (Of course this is not a finite field.) — MFH:Talk 20:32, 21 May 2007 (UTC)

[edit] Question concerning the equivalence of QR and integer factoring

The text claims that QR for composite n and integer factoring are equivalent. It is clear that a polynomial time algorithm for integer factoring implies a polynomial time for QR. But how does the opposite direction work, i.e., how can we obtain a polynomial time algorithm for integer factoring from a polynomial time algorithm for QR? Could anybody give a hint or provide a reference? Desi73 (talk) 10:10, 5 December 2007 (UTC)

I'm too lazy to dig up a reference, there may be some in Rabin cryptosystem. First of all, the claim is being made for algorithms finding square roots (rather than the QR decision problem), and the reduction is randomized, so it gives a probabilistic poly-time algorithm for factoring, not a deterministic one.
The basic idea is as follows: if n is odd, and it is not a perfect power, then every quadratic residue has at least 4 square roots mod n. Thus if you pick a random a, and apply your alleged root finding algorithm to a2, it will output with probability at least 1/2 a root b which is different from ±a. That is, b^2\equiv a^2\pmod n, but b\not\equiv\pm a\pmod n. Then it is easy to see that \gcd(n,a\pm b) gives a nontrivial divisor of n. -- EJ (talk) 11:44, 5 December 2007 (UTC)
This is convincing. Thanks a lot. -- Desi73 (talk) 14:52, 5 December 2007 (UTC)


[edit] A new section?

The text provides a link to acoustics where presumably residues are used as some kind of source of randome numbers. But the linked article says nothing about that.

Instead of a link to "Distribution of quadratic residues" I will add a new section. Keeping the links to acoustics and crypto, and covering Jacobi-Dirichlet and Polya-vinogradov. Virginia-American (talk) 02:52, 26 February 2008 (UTC)

I will also add stuff about how different the theory is depending on whether the moduls is prime or not (eg, one can solve x2 ≡ a (mod p), but mod a composite it is basically factoring the modulus. —Preceding unsigned comment added by Virginia-American (talk • contribs) 17:50, 26 February 2008 (UTC)

I have basically rewritten the article - it's in User:Virginia-American/Sandbox. Is there anything required, customary or courteous to do before I copy it over? Virginia-American (talk) 19:57, 27 February 2008 (UTC)

Dear Virginia-American, welcome to Wikipedia. Your rewrite is very nice. It is applaudable that you are seeking approval of other editors before making such a sweeping change, but generally you do not have to worry about notifying people, just be bold. At any rate, it is sufficient to leave a note here on the article talk page, as anybody who cares about the article is supposed to have it on their watchlist. -- EJ (talk) 14:08, 29 February 2008 (UTC)
Thanks, EJ. It's done. Another question (the documentation here is overwhelming, I know I've seen the answer somewhere but I can't remember where). There are a bunch of references at the bottome to foreign languges, most of which I don't know. How/when do articles get translated? Virginia-American (talk) 18:07, 29 February 2008 (UTC)
I glanced over your rewrite as well, and it's well-written and comprehensive. Welcome and I hope your future contributions are as great as this one! Dcoetzee 18:18, 29 February 2008 (UTC)
Thanks for the kind words, Dcoetzee. Is there any way to tell who is watching a page? —Preceding unsigned comment added by Virginia-American (talk • contribs) 01:18, 1 March 2008 (UTC)
Nope, there's not - otherwise vandals would be able to identify pages to vandalize that wouldn't get noticed (although there is Special:UnwatchedPages, only visible by admins). To answer your questions about article translation, most articles on different language projects are independently written, but there are some ad hoc translation projects. Please feel free to leave any other questions you have on my talk page, and remember to sign your talk page comments with four tildes (~~~~). Dcoetzee 04:22, 1 March 2008 (UTC)

[edit] Perfect ?

What do "square" and "perfect square" differ? Virginia-American (talk) 19:07, 9 April 2008 (UTC)

They don't, AFAICS. The anon's change was misguided, though harmless. — EJ (talk) 12:08, 10 April 2008 (UTC)

[edit] Consistency

I don't like the anonymous editor's last change:

I had said that every integer is a QR (mod 2); he said

Modulo 2, only 1 is considered a quadratic residue.

I went on to say

Modulo an odd prime number p there are (p + 1)/2 residues (including 0) and (p − 1)/2 nonresidues. In this case, it is customary to consider 0 as a special case and work within the multiplicative group of nonzero elements of the field Z/pZ. (In other words, every congruence class except zero (mod p) has a multiplicative inverse. This is not true for composite moduli.)[4]

Following this convention, the multiplicative inverse of a residue is a residue, and the inverse of a nonresidue is a nonresidue.[5]

This is inconsistent. I'd just revert it, but I don't want to get into an edit war over something fairly peripheral. Virginia-American (talk) 21:03, 7 June 2008 (UTC)