Talk:Congruence of squares

Square roots

The claim that finding square roots in a finite field is equivalent to factoring is incorrect. In fact, finding square roots in a finte field is easy. Here is a link to an interactive web page that does it:

[1]

Finding square roots (mod N) where N is not prime *IS* equivalent to factoring.

The confusion stems from the fact that the integers mod N form a field if and only if N is prime.

The article doesn't seem to mention this at present - but see Shanks-Tonelli algorithm --catslash (talk) 17:19, 25 February 2008 (UTC)

More confusion

The paragraph that begins "A case where a congruence of squares will not yield a factor..." is nonsensical. For one thing it refers to something which is an ordinary number (or possibly a residue class) as a "pair". Aside from that, if we're already assuming that x is not congruent to plus/minus y (mod n), then why go on to consider the possibility that n divides one of x+y and x-y? This possibility is explicitly excluded. Do correct me if I'm wrong. I'll check back later on and delete the offending paragraph unless someone has done so already, or pointed out my mistake. Buster79 11:03, 28 March 2006 (UTC)

Hmm, did I write that? Quite strident. I'll make a few changes to the paragraph, instead of deleting it. Buster79 02:53, 6 April 2006 (UTC)

Good chance?

Currently the article says There is a good chance that n will have common factor(s) with (x + y) (x − y). Looking at the history, I find it used to say This means that n divides (x+y)(x−y) but not (x+y) or (x−y) alone, so both (x+y) and(x−y) contain factors of n. Which seems to make more sense - but then it adds A simple gcd operation will extract a factor in most cases. Why only most??? --catslash (talk) 23:42, 16 February 2008 (UTC)

OK: I've changed it to something similar to what was in the history (but with more emphasis on x and y not being congruent). --catslash (talk) 17:08, 25 February 2008 (UTC)

Example: x=3, y=2 and n=5 --> so "n" divides (x+y) alone [5 divides 5]. I would remove the "but not (x+y) or (x−y) alone" or change it for sth like "but not (x+y) and (x−y), both individually". Sorry for bad english. Iván. —Preceding unsigned comment added by 190.174.134.14 (talk) 06:22, 12 September 2009 (UTC)

Your English is fine. The article specifies that $x\not \equiv \pm y{\pmod {n}}$, but $2\equiv -3{\pmod {5}}$, so your example is not considered a valid congruence of squares. However in practice, one would search for x and y, satisfying $x^{2}\equiv y^{2}{\pmod {n}}$, and then check that x and y were different (or simply try to see if they give a proper factor) - so the procedure could fail at this stage. Perhaps the article should explain this. --catslash (talk) 11:40, 20 September 2009 (UTC)