Diophantine equation y^2=x^3-2*x+1
- To: mathgroup at smc.vnet.net
- Subject: [mg30672] Diophantine equation y^2=x^3-2*x+1
- From: Ranko Bojanic <bojanic at math.ohio-state.edu>
- Date: Mon, 3 Sep 2001 20:32:50 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
On Saturday,September 1,2001,at 08:58 AM, Adrian Spalka wrote:
>hi,
>how can i tell mathematica to compute all solutions of an equation in two
>variables in Fp?
>eg,to compute all solutions of
>y^2=x^3-2*x+1 in F13,ie with x,y in[0,...,12]
>thanks.
>adrian
Andrzej Kozlowski suggested a very nice and simple solution:
solAK[p_]:=
DeleteCases[({x->#1,
Solve[{y^2==#1^3-2 #1+1,Modulus==p},y,
Mode->Modular]}&)/@
Range[0,p-1]/.{Modulus->p,z_}->z,{z_,{}},Infinity];
I suggested then a small improvement of this method by using
only those numbers x in [0,p-1] for which x^3-2*x+1 is a
quadratic residue:
solRB[p_]:=Module[{y,testList,goodList,res},
testList = Range[0,p-1]^3 - 2 Range[0,p-1]+1;
goodList=Delete[Range[0,p-1],Position[JacobiSymbol[testList,p],-1]];
res=Map[Solve[{y^2==#, Modulus==p},y,Mode->Modular]&,
goodList^3 - 2 goodList + 1];
res=Delete[res,Position[res,Modulus->p]];
Return[{goodList,y/.res}//Transpose]]
I wrote also that further improvements are not likely, which was wrong.
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]]
Here is a comparison of speeds of all three algorithms:
solAK[7919];//Timing
{118.733 Second, Null}
solRB[7919];//Timing
{93.1833 Second,Null}
sol[7919]; // Timing
{4.65 Second, Null}
Ranko