       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.

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

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;//Timing
{118.733 Second, Null}

solRB;//Timing
{93.1833 Second,Null}

sol; // Timing
{4.65 Second, Null}

Ranko

```

• Prev by Date: Re: Fitting data to line with a specific slope
• Next by Date: Diophantine equation y^2=x^3-2*x+1
• Previous by thread: Re:convert graphics
• Next by thread: Diophantine equation y^2=x^3-2*x+1