Group of Points
We shall work with projective coordinates. [Briefly: we adjoin a bunch of points at infinity (which together make up a line at infinity) so that it is always true that every two distinct points determine a line and every two distinct lines intersect at a single point. For example, lines that are parallel under affine coordinates will intersect at a particular point at infinity. TODO: projective geometry notes]
It turns out that there is a group structure on the solutions of elliptic curve equations which we shall describe below. It is a finite abelian group where the discrete log problem is believed to be hard, making it ideal for cryptography. Moreover, the best known algorithms for solving discrete log on these groups are algorithms that work on generic groups, which have significantly longer running times than the specialized algorithms focusing on discrete log in finite fields. Lastly, a nondegenerate bilinear pairing exists for this group, and many cryptosystems would not exist without it.
Chord-Tangent Composition
When in (projective) Weierstrass form, an elliptic curve always contains exactly one point of infinity, \((0, 1, 0)\) ("the point at the ends of all lines parallel to the \(y\)-axis"), and the tangent at this point is the line at infinity and intersects the curve at \((0,1,0)\) with multiplicity three.
It turns out that every line intersects the curve at exactly three points (counting multiplicities).
Let the point \(O\) be some point of an elliptic curve. (i.e. the coordinates \(x, y\) of \(O\) satisfy a particular cubic equation). Suppose \(P\) and \(Q\) are two points of an elliptic curve. The line through \(P\) and \(Q\) intersects the curve at a third point \(R\). (If \(P = Q\) then we are considering the tangent at \(P\).) As we are working in projective coordinates each line intersects a cubic at exactly three points guaranteeing the existence and uniqueness of \(R\). Now consider the line through \(R\) and \(O\). This intersects the curve at a third point which we shall call \(P + Q\).
Next, take the tangent at \(O\). It intersects the curve at another point which we shall call \(OO\). Now the line through \(P\) and \(OO\) intersects at a third point. Call this point \(-P\).
It can be verified that
-
\(P + Q = Q + P\)
-
\(P + O = P\)
-
\((-P) + P = O\)
and hence the set of points forms an Abelian group, justifying our use of the \(+\) symbol.
By convention, we take \(O\) to be the point at infinity \((0,1,0)\) (thus \(OO\) is also this point, which is convenient).