Computing point operations on an elliptic curve over a finite field [duplicate]

Question

I'm working on a homework problem that asks you to compute $1943(1980,431)$, where $p = 2671$, $E:Y^2=X^3+171X+853$, and $P=(1980,431) \in E(F_{2671})$.

I found the ternary expansion of $1943$ to be $1943=-2^0-2^3+2^5-2^7+2^{11}$. Thus $1943P=-P-2^3P+2^5P-2^7P+2^{11}P$, so computing $1943P$ using the double-and-add algorithm requires $11$ doublings and $4$ additions. However, this seems inefficient to do by hand.

How do I use Mathematica to compute point operations on an elliptic curve?

Answer 1

There probably is some way to do this using built-in functionality, but anyhow, here is an implementation of the group law (use at your own risk):

add[a_][P:{xP_,yP_},Q:{xQ_,yQ_}]:=If[And[xP===xQ,yP===-yQ],Infinity,
  With[{s=If[xP===xQ,(3*xP^2+a)/(2*yP),(yP-yQ)/(xP-xQ)]},
    With[{xR=s^2-xP-xQ},
      {xR,-yP-s*(xR-xP)}]]];
add[a_][Infinity,Infinity]=Infinity;
add[a_][Infinity,Q_]:=Q;
add[a_][P_,Infinity]:=P;

add[a_][P_]:=P;
add[a_][P_,Q_,Ps__]:=add[a][add[a][P,Q],Ps];

mult[a_][n_Integer/;n>=0,P_]:=With[{ds=IntegerDigits[n,2]},
  add[a]@@Pick[NestList[add[a][#,#]&,P,Length[ds]-1]//Reverse,ds,1]];

We can now calculate:

Needs["FiniteFields`"];
kk=GF[2671][{#}]&;

(* elliptic curve *)
a=kk[171];
b=kk[853];
e[{x_,y_}]:=y^2-(x^3+a*x+b);

(* calculation requested by OP *)
P={kk[1980],kk[431]};

(* 1st method, slow *)
Q=add[a]@@ConstantArray[P,1943]

(* 2nd method, faster *)
Q=mult[a][1943,P]

(* check that we are still on the curve *)
e[Q]
(* 0 *)

Both methods give the following result for Q:

{GF[2671, {0, 1}][{1432}], GF[2671, {0, 1}][{667}]}

that is $(1432,667)$.

---

Discrete log. This is naive code that tries to find an integer $n\geq 0$ such that $nP=Q$:

discreteLog[a_][P_,Q_]:=First[NestWhile[{#[[1]]+1,add[a][P,#[[2]]]}&,
                                        {0,Infinity},(#[[2]]=!=Q)&]];

(* Example using same points as before *)
discreteLog[a][{kk[1980],kk[431]},{kk[1432],kk[667]}]
(* 624 *)

See also this answer from 2015.