       Diophantine equation y^2=x^3-2*x+1

• To: mathgroup at smc.vnet.net
• Subject: [mg30666] 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:40 -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];

Here are some timings for this function on my 400 Mhz PowerBook G3:

solAK//Timing
{0.05 Second,{{x->0,{y->1,y->12}},{x->1,{y->0,y->0}},{x->3,{y->3,y->10}},
{x->5,{y->5, y->8}},{x->6,{y->6,y->7}},{x->8,{y->4,y->9}},{x->9,{y->6,y->7}},
{x->11,{y->6,y->7}}}}

solAK;//Timing
{7.18333 Second,Null}

solAK;//Timing
{118.733 Second, Null}

For this equation, and all equations of the form y^2 = P[x] where P[x] is
a polynomial, the algorithm can be accelerated a little if we do not try
to solve the equation y^2=x^3-2*x+1 for all x in Range[0,p-1], but only
for those x for which x^3-2*x+1 is a quadratic residue in Zp:

solRB[p_]:=Module[{y,testList,goodList,res},
testList = Range[0,p-1]^3 - 2Range[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]]

Here we delete from Range[0,p-1] all numbers x for which x^3-2*x+1 is
a quadratic non-residue. What remains, are all numbers x such that
x^3-2*x+1 is a quadratic residue or 0 (when x = 1}.

The timings are

solRB//Timing
{0.0333333 Second,{{0,{1,12}},{1,{0,0}},{3,{3,10}},
{5,{5,8}},{6,{6,7}},{8,{4,9}},{9,{6,7}},{11{6,7}}

solRB;//Timing
{4.7 Second,Null}

solRB;//Timing
{93.1833 Second,Null}

The number 1223 is Prime and 7919 is Prime. I do not
think that  essentially faster algorithms for the solution of the
Diophantine equation y^2=x^3-2*x+1 in Zp exist, but then with
Mathematica everything is possible

Ranko

```

• Prev by Date: Diophantine equation y^2=x^3-2*x+1
• Next by Date: Sticky Previews? Mathematica Export, Illustrator, and Textures
• Previous by thread: Diophantine equation y^2=x^3-2*x+1
• Next by thread: Sticky Previews? Mathematica Export, Illustrator, and Textures