Re: Square Roots mod n (n composite)
- To: mathgroup at smc.vnet.net
- Subject: [mg25099] Re: [mg25071] Square Roots mod n (n composite)
- From: Andrzej Kozlowski <andrzej at bekkoame.ne.jp>
- Date: Fri, 8 Sep 2000 03:00:45 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
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:
<http://www.sstreams.com/Mathematica/>
on 00.9.8 11:28 AM, Matt Herman at Henayni at hotmail.com 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
>
>