Talk:Congruence of squares
From Wikipedia, the free encyclopedia
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:
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.
[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)
