MathGroup Archive 2000

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

Search the Archive

Re: Square Roots mod n (n composite)

  • To: mathgroup at
  • Subject: [mg25099] Re: [mg25071] Square Roots mod n (n composite)
  • From: Andrzej Kozlowski <andrzej at>
  • Date: Fri, 8 Sep 2000 03:00:45 -0400 (EDT)
  • Sender: owner-wri-mathgroup at

It seems to me that the simplest (and perhaps the fastest) way is to use
Solve. For example the following code will find all square roots mod 125 of
all the numbers of Range[124] and output them in TableForm:

DeleteCases[Map[{#, Solve[{x^2 - # == 0, Modulus == 125}]} &, Range[124]],
    Rule[Modulus, 125], Infinity] // TableForm

I am not sure, however, if this will work for very large n.

Andrzej Kozlowski
Toyama International University, JAPAN

For Mathematica related links and resources try:

on 00.9.8 11:28 AM, Matt Herman at Henayni at wrote:

> 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

  • Prev by Date: Re: NotebookSave
  • Next by Date: Re: Manipulating Equations
  • Previous by thread: Square Roots mod n (n composite)
  • Next by thread: Re: Square Roots mod n (n composite)