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