Re: Square Roots mod n (n composite)
- To: mathgroup at smc.vnet.net
- Subject: [mg25112] Re: [mg25071] Square Roots mod n (n composite)
- From: Andrzej Kozlowski <andrzej at bekkoame.ne.jp>
- Date: Sun, 10 Sep 2000 03:14:35 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
Yes, I remember now that Solve (and some other algebraic Mathematica
functions) have always refused to work modulo very large primes. I have also
noticed that Stan Wagon includes a code for a function he calls SqrtModAll
in his book "Mathematica in Action". This function does exactly what you
want to do. Unfortunately his algorithm is the same as yours, in other
words: solve the problem module prime powers and use the Chinese Reminder
Theorem. I can send it to you if you do not have the book and want to see
it, but since the algorithm is the same as yours, even if Stan's
implementation turned out to be somewhat more efficient it would not
constitute a significant speed up. All this suggests to me that at this time
there is no better method. I am not sure if the limitations in Solve are
really due to some fundamental mathematical difficulty or just the current
implementation. I vaguely remember that Daniel Lichtblau once made some
remarks on the subject but without clearly stating that these limitations
would be removed (if indeed it is possible).
Andrzej
on 00.9.8 8:11 PM, Matt Herman at Henayni at hotmail.com wrote:
> Andrzej,
>
> That code doesn't work for larger inputs.
>
> sqmdal[d_, n_] :=
> x /. Partition[Transpose[Solve[{x^2 - d == 0, Modulus == n}]][[2]], 1]
>
> In[57]:=
> sqmdal[2, 12351235121^2 - 2*127^2]
> From In[57]:=
> Roots::"badmod": "Cannot extract roots of input modulo \
> \!\(152553009014223852383\)."
> From In[57]:=
> Roots::"badmod": "Cannot extract roots of input modulo \
> \!\(152553009014223852383\)."
> From In[57]:=
> \!\(Transpose::"nmtx" \(\(:\)\(\ \)\)
> "The first two levels of the one-dimensional list \
> \!\({\(ToRules[\(\(\(\(Modulus == 152553009014223852383\)\) &&
> \(\(Roots[\(\(\
> \(\(x\^2 == 2\)\), x, \(\(Modulus -> \
> 152553009014223852383\)\)\)\)]\)\)\)\)]\)}\) cannot be transposed."\)
> From In[57]:=
> \!\(Part::"partw" \(\(:\)\(\ \)\)
> "Part \!\(2\) of \!\(Transpose[\(\({\(ToRules[\(\(\(\(Modulus == \
> 152553009014223852383\)\) && \(\(Roots[\(\(\(\(x\^2 == 2\)\), x, \(\(Modulus
> \
> -> 152553009014223852383\)\)\)\)]\)\)\)\)]\)}\)\)]\) does not exist."\)
> From In[57]:=
> \!\(Part::"partw" \(\(:\)\(\ \)\)
> "Part \!\(2\) of \!\(Transpose[\(\({\(ToRules[\(\(\(\(Modulus == \
> 152553009014223852383\)\) && \(\(Roots[\(\(\(\(x\^2 == 2\)\), x, \(\(Modulus
> \
> -> 152553009014223852383\)\)\)\)]\)\)\)\)]\)}\)\)]\) does not exist."\)
> From In[57]:=
> \!\(ReplaceAll::"reps" \(\(:\)\(\ \)\)
> "\!\({\(\(\(Transpose[\(\({\(ToRules[\(\(\(\(Modulus == \
> 152553009014223852383\)\) && \(\(Roots[\(\(\(\(x\^2 == 2\)\), x, \(\(Modulus
> \
> -> 152553009014223852383\)\)\)\)]\)\)\)\)]\)}\)\)]\)\) \[LeftDoubleBracket]
> 2 \
> \[RightDoubleBracket]\)}\) is neither a list of replacement rules nor a
> valid \
> dispatch table, and so cannot be used for replacing."\)
> Out[57]=
> \!\(x /. \[InvisibleSpace]\(Transpose[{ToRules[
> Modulus == 152553009014223852383 &&
> Roots[x\^2 == 2, x,
> Modulus ->
> 152553009014223852383]]}]\)\[LeftDoubleBracket]2\
> \[RightDoubleBracket]\)
>
>
>
> In[55]:=
> SqrtMod[2, 12351235121^2 - 2*127^2]
> Out[55]=
> 67132179053880245224
>
>
> As you can see, the squareroot of 2 does exist modulo x^2-2y^2, but an error
> message is generated by Solve.
>
> Matt
>
>
> ----- Original Message -----
> From: "Andrzej Kozlowski" <andrzej at bekkoame.ne.jp>
To: mathgroup at smc.vnet.net
> To: "Matt Herman" <Henayni at hotmail.com>; <mathgroup at smc.vnet.net>
> Sent: Friday, September 08, 2000 2:37 AM
> Subject: [mg25112] Re: [mg25071] Square Roots mod n (n composite)
>
>
>> 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
>>>
>>>
>>
>>
>>
--
Andrzej Kozlowski
Yokohama, JAPAN
http://platon.c.u-tokyo.ac.jp/andrzej/
http://sigma.tuins.ac.jp/