MathGroup Archive 2001

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

Search the Archive

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

  • To: mathgroup at
  • Subject: [mg30672] Diophantine equation y^2=x^3-2*x+1
  • From: Ranko Bojanic <bojanic at>
  • Date: Mon, 3 Sep 2001 20:32:50 -0400 (EDT)
  • Sender: owner-wri-mathgroup at

On Saturday,September 1,2001,at 08:58 AM, Adrian Spalka wrote:

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

Andrzej Kozlowski suggested a very nice and simple solution:

                Solve[{y^2==#1^3-2 #1+1,Modulus==p},y,

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:

             testList = Range[0,p-1]^3 - 2 Range[0,p-1]+1;
 res=Map[Solve[{y^2==#, Modulus==p},y,Mode->Modular]&, 
                                             goodList^3 - 2 goodList + 1];
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:

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:
{118.733 Second, Null}

{93.1833 Second,Null}

sol[7919]; // Timing
{4.65 Second, Null}


  • 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