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