       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}]][], 1]

In:=
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=
\!\(x /. \[InvisibleSpace]\(Transpose[{ToRules[
Modulus == 152553009014223852383 &&
Roots[x\^2 == 2, x,
Modulus ->
152553009014223852383]]}]\)\[LeftDoubleBracket]2\
\[RightDoubleBracket]\)

In:=
SqrtMod[2, 12351235121^2 - 2*127^2]
Out=
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 and output them in TableForm:
>
> DeleteCases[Map[{#, Solve[{x^2 - # == 0, Modulus == 125}]} &, Range],
>     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
> >
> >
>
>
>

```

• Prev by Date: Re: Need Help With Simple Animation
• Next by Date: Re: Square Roots mod n (n composite)
• Previous by thread: Re: Square Roots mod n (n composite)
• Next by thread: Re: Square Roots mod n (n composite)