Square Roots mod n (n composite)

*To*: mathgroup at smc.vnet.net*Subject*: [mg25071] Square Roots mod n (n composite)*From*: "Matt Herman" <Henayni at hotmail.com>*Date*: Thu, 7 Sep 2000 22:28:15 -0400 (EDT)*Sender*: owner-wri-mathgroup at wolfram.com

Hi, I want to generate all squareroots of d (modulo n) where n is composite. Assuming I have factored n into p1^a1 * p2^a2 *** pk^ak. I then take the squareroots of d modulo each of the pi^ai. Then I use the chineseremainder theorem on those squareroots and their negatives. This gets slow, because you need to use the CRT 2^k times. Does anyone have a better method? (this has to do with finding all "fundamental solutions" to x^2+dy^2=n and x^2-dy^2=n) Matt