I'm trying to work out a problem from a previous exam in Cryptography regarding elliptic curves. I can add points on an EC using the formulas given, but the suggested solution to this exam problem I cannot understand.
The EC is given by $E:Y^{2} = X^{3} + X + 46$ over $\mathbb{F}_{101}$, and I'm given three points, $P = (2,37)$, $Q = (54,2)$ and $R = (64,19)$ I'm supposed to show that $$6P + 2Q + R = \infty$$ $$2P + Q + 2R = \infty$$
$\infty$ being the identity or zero/neutral element of the corresponding group. I tried to compute the addition of the points to itself and see if some inverses turned up, but I might have made a mistake because I couldn't find such a property. The suggested solution however talks about doublings and addition, and the cost of these operations. I don't really understand how that plays a part, and nowhere in the solution do they compute anything so I'm really unsure how they arrive at the correct conclusion. Some help would be appreciated.
EDIT: Someone asked to see the suggested solution, but I couldn't figure out how to format it correctly, so I'll give a link to it. It's the answer to problem 3b). https://wiki.math.ntnu.no/_media/tma4160/losning2013.pdf
I was disposed to solve your question but the point $R=(63,19)$ does not belong to the curve $E$ so have no sense neither, the addition with $R$ nor the duplication point $2R$.
If you edit your post, I could give an answer maybe. I wonder a related problem could be find the point $R=(x,y)$ in order to have your relations (not forgetting that $ nP $ is given by a polynomial formula of degree $ n ^ 2 $). It would be convenient, if you edit, say that your $\infty$ is assumed to be the zero of the corresponding group.
NOTE.- I hope, anyway, not to be wrong saying $R\notin E$
ADDENDUM.-This question only requires calculations with formulas defining the law of the group $E$, calculations in the finite field $\mathbb F_{101}$ which may be somewhat laborious task. It seems to me that AT LEAST ONE OF THE TWO GIVEN RELATIONS IS WRONG! because calculating $-Q = 2 (P + R)$ and $2P = 3R$ (this last relation implicated by elimination of $Q$) not give me the correct verification in both cases. I give here the calculation of $2(P+Q)$ which results distinct of $-Q$. If I am wrong in this calculation (with some frequency it happens to me) I think what is important is to see clearly the way this kind of problems in the realm of elliptic curves is solved.
Then $R=(64,19), P=(2,37), Q=(54,2)$, so $-Q=(54,-2)$ lie in the curve $E: Y^2=X^3+X+46$ and it is asked to verified the relations $$6P+2Q+R=0….(1)$$ and $$2P+Q+2R=0….(2)$$ I have to use the formulas defining the group $E: y^2=x^3+Ax+B$.
If $P_i=(x_i,y_i); i=1,2$ then $P_1+P_2=(x_3,y_3)$
with $$x_3=m^2-x_1-x_2$$ and $$y_3=m(x_1-x_3)-y_1$$ where $$m=\frac{y_2-y_1}{x_2-x_1}\text{ when}\space\space P_1\ne P_2$$ and $$m=\frac{3x_1+A}{2y_1}\text{ when}\space\space P_1=P_2$$.
We calculate in detail with
$\boxed{2P+Q+2R=0\iff –Q=2(P+R)}$
►$P+R=(x,y)=?$
$m=\frac{19-37}{64-2}=\frac{-9}{31}$ then $$x=(\frac{-9}{31})^2-64-2=\frac{81-66\cdot(31)^2}{(31)^2}=\frac{-63345}{961}=\frac{-(627\cdot101+18)}{9\cdot101+52}=\frac{-18}{52}=\frac{-9}{26}=-9\cdot35=-315=-12$$ $$y=(\frac{-9}{31})(2-(-12))-37=\frac{-9\cdot14-31\cdot37}{31}=\frac{-1273}{31}=\frac{-(12\cdot101+61)}{31}=\frac{-61}{31}=-61\cdot88=-61(-13)=793=7\cdot101+86=86=-15$$ Thus $P+R=(-12,-15)$
►$2(P+R)=2(-12,-15)=(x,y)=?$
$m=\frac{3(-12)+1}{2(-15)}=\frac{-35}{-30}=\frac76$ then $$x=(\frac76)^2-2(-12)=\frac{49+36\cdot24}{36}=\frac{913}{36}=913\cdot87=4(-14)=-56=45$$ $$y=\frac76(-12-45)-(-15)=\frac{7(-57)+6\cdot15}{6}=\frac{-309}{6}=-\frac{309}{6}=\frac{-6}{6}=-1$$ Thus $2(P+R)=(45,-1)\ne(54,-2)=-Q$ which would imply that the relation (2) is false (If none error in this calculation).