Elliptic Curves

Consider an elliptic curve $E$ (in Weierstrass form)

over a field $K$.

Let $P=(x_1,y_1)$ be a point on $E(K)$.

Negation

To compute $-P$, we need to find the line through $P$ and $O$ (recall $O=\mathrm{OO}$), and find the third point of intersection. The line through $P$ and $O$ is the vertical line through $P$, so we need to find the points of intersection of $X=x_1$ and the curve. In other words, we need to solve $$Y^2+(a_1{x}_1+a_3)Y-(x_1^3+a_2{x}_1^2+a_4{x}_1+a_6)=0$$ Since we know one solution is $Y=y_1$, we know that the other must be $-a_1{x}_1-a_3-y_1$. That is, $$-P=(x_1,-a_1{x}_1-a_3-y_1)$$ Recall that if $charK\ne 2$, we can affinely transform the curve so that $a_1=a_3=0$, so that to find the inverse of $P$ we simply negate its $y$-coordinate.

Point Doubling

To find $P+P=2P$ (whose coordinate we'll denote by $(x_3,y_3)$), we need the equation of the tangent at $P$. The gradient of the tangent at the point $(X,Y)$ is given by $(\mathrm{dE}/\mathrm{dX})/(\mathrm{dE}/\mathrm{dY})=(3X^2+2a_{2}X+a_4)/(2Y+a_{1}X+a_3)$. So setting $$\lambda =\frac{3x_1^2+2a_2{x}_1+a_4}{2y_1+a_1{x}_1+a_3}$$ means the tangent at $P$ is given by the equation $Y=\lambda X-\lambda x_1+y_1$. Substituting this into the equation for $E$ and negating the coefficient of $X^2$ gives the sum of the roots: $${\lambda }^2+\lambda a_1-a_2$$ which means the $x$-coordinate of the third point of intersection must be $$x_3={\lambda }^2+\lambda a_1-a_2-2x_1$$ and the corresponding $y$-coordinate can be found from the equation of the tangent at $P$: $$y\prime =\lambda x_3-\lambda x_1+y_1$$ Lastly we need to negate $(x_3,y\prime )$ which from above is $$y_3=-a_1{x}_1-a_3-\lambda x_3+\lambda x_1-y_1$$

Point Addition

Suppose we have a second point $Q=(x_2,y_2)$ different from $P$. We wish to find $P+Q$ whose coordinates we shall denote by $(x_3,y_3)$. If $P=-Q$, then $P+Q=O$. Otherwise the gradient of the line determined by $P$ and $Q$ is $$\lambda =\frac{y_2-y_1}{x_2-x_1}$$ and the equation of the line between $P$ and $Q$ is $Y=\lambda X-\lambda x_1+y_1$. Substituting this into the curve gives the equation $$(\lambda X-\lambda x_1+y_1{)}^2+(a_{1}X+a_3)(\lambda X-\lambda x_1+y_1)=X^3+a_2{X}^2+a_{4}X+a_6$$ The sum of the roots, i.e. the negation of the coefficient of $X^2$ is ${\lambda }^2+a_1\lambda -a_2$, hence $$x_3={\lambda }^2+a_1\lambda -a_2-x_1-x_2$$ and the corresponding $y$-coordinate can be found by substituting into the equation of the $P$-$Q$ line: $$y\prime =\lambda x_3-\lambda x_1+y_1$$ As before, we must negate this third point $(x_3,y\prime )$ which from above gives $$y_3=-a_1{x}_3-a_3-\lambda x_3+\lambda x_1-y_1$$