MathGroup Archive 2000

[Date Index] [Thread Index] [Author Index]

Search the Archive

Square Roots mod n (n composite)

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


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)


  • Prev by Date: Re: what mathematical formula can generate a mobius strip?
  • Next by Date: NonlinearRegression
  • Previous by thread: Re: Graphics problem
  • Next by thread: Re: Square Roots mod n (n composite)