Re: Square Roots mod n (n composite)
- To: mathgroup at smc.vnet.net
- Subject: [mg25110] Re: [mg25071] Square Roots mod n (n composite)
- From: "Matt Herman" <Henayni at hotmail.com>
- Date: Sun, 10 Sep 2000 03:14:33 -0400 (EDT)
- References: <B5DEB84F.7983%andrzej@bekkoame.ne.jp>
- Sender: owner-wri-mathgroup at wolfram.com
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]
Roots::"badmod": "Cannot extract roots of input modulo \
\!\(152553009014223852383\)."
Roots::"badmod": "Cannot extract roots of input modulo \
\!\(152553009014223852383\)."
\!\(Transpose::"nmtx" \(\(:\)\(\ \)\)
"The first two levels of the one-dimensional list \
\!\({\(ToRules[\(\(\(\(Modulus == 152553009014223852383\)\) &&
\(\(Roots[\(\(\
\(\(x\^2 == 2\)\), x, \(\(Modulus -> \
152553009014223852383\)\)\)\)]\)\)\)\)]\)}\) cannot be transposed."\)
\!\(Part::"partw" \(\(:\)\(\ \)\)
"Part \!\(2\) of \!\(Transpose[\(\({\(ToRules[\(\(\(\(Modulus == \
152553009014223852383\)\) && \(\(Roots[\(\(\(\(x\^2 == 2\)\), x, \(\(Modulus
\
-> 152553009014223852383\)\)\)\)]\)\)\)\)]\)}\)\)]\) does not exist."\)
\!\(Part::"partw" \(\(:\)\(\ \)\)
"Part \!\(2\) of \!\(Transpose[\(\({\(ToRules[\(\(\(\(Modulus == \
152553009014223852383\)\) && \(\(Roots[\(\(\(\(x\^2 == 2\)\), x, \(\(Modulus
\
-> 152553009014223852383\)\)\)\)]\)\)\)\)]\)}\)\)]\) does not exist."\)
\!\(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
Subject: [mg25110] 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
> >
> >
>
>
>