Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

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.
>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];

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

solAK[13]//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[1223];//Timing
{7.18333 Second,Null}

solAK[7919];//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[13]//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[1223];//Timing
{4.7 Second,Null}

solRB[7919];//Timing
{93.1833 Second,Null}

The number 1223 is Prime[200] and 7919 is Prime[1000]. 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