SqrtMod function

• To: mathgroup at smc.vnet.net
• Subject: [mg30698] SqrtMod function
• From: Ranko Bojanic <bojanic at math.ohio-state.edu>
• Date: Sat, 8 Sep 2001 02:23:01 -0400 (EDT)
• Sender: owner-wri-mathgroup at wolfram.com

```On Monday, 3 Sep 2001 20:32:50, in [mg30672] "Diophantine equation
y^2=x^3-2*x+1" Ranko Bojanic wrote:

>   In the NumberTheory package, in NumberTheoryFunctions, there
>   is a fast function SqrtMod which reduces significantly the
>   speed of the algorithm:

>   <<NumberTheory`NumberTheoryFunctions`
>   sol[p_] := Module[{aList, testList, positions, goodList, res},
>          aList = Range[0, p - 1]^3 - 2 Range[0, p - 1] + 1;
>    positions = Position[JacobiSymbol[aList, p], -1];
>    testList = Delete[aList, positions];
>    goodList = Delete[Range[0, p - 1], positions];
>    res = Map[SqrtMod[#, p] &, testList];
>    res = Transpose[{res, Mod[-res, p]}];
>    Return[{goodList, res} // Transpose]]

When Mod[a,p]==0, the function SqrtMod[a,p] does not return zero,
as it should. For such a's the equation y^2=x^3-2*x+1
has trivial solution {a,0} in Zp. We have, for instance,

sol[19]
{0, {1, 18}}, {1, {0, 0}}, {2, {9, 10}}, {4, {SqrtMod[57, 19],
Mod[-SqrtMod[57, 19], 19]}}, {7, {11, 8}}, {9, {16, 3}},
{13, {5, 14}}, {14, {SqrtMod[2717, 19], Mod[-SqrtMod[2717, 19], 19]}},
{17, {4, 15}}}

This can be corrected easily by redefinig the function SqrtMod:

<<NumberTheory`NumberTheoryFunctions`

sol[p_] := Module[{y, aList, testList, positions, goodList,
res, sqMod},
sqMod = If[Mod[#, p] != 0, SqrtMod[#, p], 0] &;
aList = Range[0, p - 1]^3 - 2 Range[0, p - 1] + 1;
positions = Position[JacobiSymbol[aList, p], -1];
testList = Delete[aList, positions];
goodList = Delete[Range[0, p - 1], positions];
res = Map[sqMod, testList];
res = Transpose[{res, Mod[-res, p]}];
Return[{goodList, res} // Transpose]]

We have now

sol[19]
{{0, {1, 18}}, {1, {0, 0}}, {2, {9, 10}}, {4, {0, 0}},
{7, {11, 8}}, {9, {16, 3}}, {13, {5, 14}}, {14, {0, 0}},
{17, {4, 15}}}

Ranko

```

• Prev by Date: Re: = or := ???
• Next by Date: Re: Transparent evalaution of a notebook
• Previous by thread: Re: JLink an animated gif
• Next by thread: Re: Collect with Simplify destroys Hold