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

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?

• @user64494 In the post you linked to, the most interesting thing I see are EllipticLog and EllipticExp. But I do not see how they are applicable to the question at hand (an elliptic curve over a finite field) or why this question would be a duplicate of that question. Can you explain? 3 people have agreed with you, so maybe I am missing something. Nov 21, 2022 at 12:41
• Hi. I just saw that you edited the title. If you have an interest in getting this reopened, then you should edit your post and write a sentence or two that directly addresses why this thread does not answer your question. Your question was first closed by 5 people, and an attempt to reopen was denied by another 3 people, so it is not going to work unless you explain with some clarity why this is not a duplicate. The title edit does help a little bit but is probably not enough. Nov 26, 2022 at 11:23
• @user293787 I ran into a problem when computing $(3,6)+(3,1)$ in $E(F_7):Y^2=X^3+2X+3$. Because x1=x2 and y1=-y2, $(3,6)+(3,1)=O$ but the code outputs $(3,6)+(3,1)=(6,0)$. Dec 12, 2022 at 7:11
• No it does not, I just tried, it gives Infinity, which is your $O$. Dec 12, 2022 at 7:35
• Not +, it should be add[a][{kk[3], kk[6]}, {kk[3], kk[1]}]. Will not be able to provide more help. You can always ask a new question if you want. Good luck. Dec 12, 2022 at 12:06

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)}]]];

mult[a_][n_Integer/;n>=0,P_]:=With[{ds=IntegerDigits[n,2]},


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 *)

(* 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 *)


• You cannot simply write 1943*P since that will do something else. Use add[a]@@ConstantArray[P,1943] instead (you can create a shorthand for this kind of thing if necessary) or the second method using doublings. Nov 19, 2022 at 14:54
• Using add[a]@@ConstantArray[P,1943] gives the following If[False, Missing["NotStored"], If[19998936696054143456 === $SessionID, Out[23], Message[ MessageName[Syntax, "noinfoker"]]; Missing["NotAvailable"]; Null]] Nov 19, 2022 at 16:18 • The output gives a box containing "add[{171}_2671] and a list of identical numbers {1980}_2671 and {431}_2671. Nov 19, 2022 at 16:25 • If I Quit[] to make sure that no previous definitions interfere, then copy & paste the code I posted here into a notebook (all of it, including the definition of add`, and in the order I posted it) then I get the result$(1432,667)\$. I use version 12.3. Nov 19, 2022 at 16:28