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