I don't know Rabin's public key algorithm, but if you could efficiently do square roots mod n = pq (without knowing p and q), you could easily factor n: Pick a random number r mod n. Square it. Using the alleged square root algorithm, take the square root, say s. With probability 1/2, s would be neither r nor -r, so (r+s)(r-s) would be 0 mod n, but neither factor would be 0. So gcd(r+s,n) and gcd(r-s,n) would be p and q in some order. The RSA public key algorithm depends on factoring being hard. --ms -----Original Message----- From: math-fun-bounces+ms=alum.mit.edu@mailman.xmission.com [mailto:math-fun-bounces+ms=alum.mit.edu@mailman.xmission.com]On Behalf Of Mike Stay Sent: Thursday, January 06, 2005 21:08 To: dasimov@earthlink.net; math-fun Subject: Re: [math-fun] Modular square root Rabin's public key algorithm is based on the difficulty of computing square roots mod n=p*q, p,q prime. ----- Original Message Follows -----
Except for semicolons, Michael Kleber writes:
<< [T]here will be at most two [square roots of an integer mod p].
Working mod p, you can still do a^2=b^2; a^2-b^2=0; (a+b)(a-b)=0; a=b or a=-b, since there are no zero divisors mod p. >>
There's something different and interesting going on with square roots in the integers mod n for n not prime, and especially if n|24.
--Dan _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com
http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay staym@clear.net.nz http://www.cs.auckland.ac.nz/~msta039 _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun