Talk:Congruence of squares

From Wikipedia, the free encyclopedia

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

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

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