The Group Structure on an Elliptic Curve

Let $E$ be an elliptic curve over a field $K$ , given by an equation $y^2=x^3+ax+b$ . We begin by defining a binary operation $+$ on $E(K)$ .

Algorithm 6.2 (Elliptic Curve Group Law)   Given $P_1, P_2\in E(K)$ , this algorithm computes a third point $R=P_1+P_2 \in E(K)$ .

1. [Is $P_i=\O$ ?] If $P_1=\O$ set $R=P_2$ or if $P_2=\O$ set $R=P_1$ and terminate. Otherwise write $(x_i,y_i)=P_i$ .
2. [Negatives] If $x_1 = x_2$ and $y_1 = -y_2$ , set $R=\O$ and terminate.
3. [Compute $\lambda$ ]Set $$\lambda = \begin{cases} (3x_1^2+a)/(2y_1) & \text{if }P_1 = P_2,\\ (y_1-y_2)/(x_1-x_2) & \text{otherwise.} \end{cases}$$
   
4. [Compute Sum] Then $R = \displaystyle \left(\lambda^2 -x_1 - x_2, -\lambda x_3 - \nu\right)$ , where $\nu = y_1 - \lambda x_1$ and $x_3=\lambda^2 -x_1 - x_2$ is the $x$ -coordinate of $R$ .

Note that in Step 3 if $P_1=P_2$ , then $y_1\neq 0$ ; otherwise, we would have terminated in the previous step.

Theorem 6.2   The binary operation $+$ defined above endows the set $E(K)$ with an abelian group structure, in which $\O$ is the identity element.

Before discussing why the theorem is true, we reinterpret $+$ geometrically, so that it will be easier for us to visualize. We obtain the sum $P_1+P_2$ by finding the third point $P_3$ of intersection between $E$ and the line $L$ determined by $P_1$ and $P_2$ , then reflecting $P_3$ about the $x$ -axis. (This description requires suitable interpretation in cases 1 and 2, and when $P_1=P_2$ .) This is illustrated in Figure 6.3, in which $(0,2)+(1,0) = (3,4)$ on $y^2=x^3-5x+4$ . To further clarify this geometric interpretation, we prove the following proposition.

Proposition 6.2 (Geometric group law)   Suppose $P_i=(x_i,y_i)$ , $i=1,2$ are distinct point on an elliptic curve $y^2=x^3+ax+b$ , and that $x_1\neq x_2$ . Let $L$ be the unique line through $P_1$ and $P_2$ . Then $L$ intersects the graph of $E$ at exactly one other point

$$Q = \left(\lambda^2 -x_1 - x_2,\quad \lambda x_3 + \nu\right),$$

where $\lambda = (y_1-y_2)/(x_1-x_2)$ and $\nu = y_1 - \lambda x_1$ .

Proof. The line $L$ through $P_1$ , $P_2$ is $y = y_1 + (x-x_1)\lambda$ . Substituting this into $y^2=x^3+ax+b$ we get

$$(y_1+(x-x_1)\lambda)^2 = x^3 + ax + b.$$

Simplifying we get $f(x) = x^3 - \lambda^2 x^2 + \cdots = 0$ , where we omit the coefficients of $x$ and the constant term since they will not be needed. Since $P_1$ and $P_2$ are in $L\cap E$ , the polynomial $f$ has $x_1$ and $x_2$ as roots. By Proposition 2.5.3, the polynomial $f$ can have at most three roots. Writing $f=\prod(x-x_i)$ and equating terms, we see that $x_1+x_2 + x_3 = \lambda^2$ . Thus $x_3=\lambda^2 -x_1 - x_2$ , as claimed. Also, from the equation for $L$ we see that $y_3 = y_1 + (x_3 - x_1)\lambda = \lambda x_3 + \nu$ , which completes the proof. $\qedsymbol$

Figure 6.3: The Group Law: $(1,0)+(0,2)=(3,4)$ on $y^2=x^3-5x+4$

To prove Theorem 6.2.2 means to show that $+$ satisfies the three axioms of an abelian group with $\O$ as identity element: existence of inverses, commutativity, and associativity. The existence of inverses follows immediately from the definition, since $(x,y)+(x,-y)=\O$ . Commutativity is also clear from the definition of group law, since in parts 1-3, the recipe is unchanged if we swap $P_1$ and $P_2$ ; in part 4 swapping $P_1$ and $P_2$ does not change the line determined by $P_1$ and $P_2$ , so by Proposition 6.2.3 it does not change the sum $P_1+P_2$ .

It is more difficult to prove that $+$ satisfies the associative axiom, i.e., that $(P_1+P_2)+P_3 = P_1 + (P_2 + P_3)$ . This fact can be understood from at least three points of view. One is to reinterpret the group law geometrically (extending Proposition 6.2.3 to all cases), and thus transfer the problem to a question in plane geometry. This approach is beautifully explained with exactly the right level of detail in [#!silvermantate!#, §I.2]. Another approach is to use the formulas that define $+$ to reduce associativity to checking specific algebraic identities; this is something that would be extremely tedious to do by hand, but can be done using a computer (also tedious). A third approach (see e.g. [#!silverman:aec!#] or [#!hartshorne!#]) is to develop a general theory of ``divisors on algebraic curves'', from which associativity of the group law falls out as a natural corollary. The third approach is the best, because it opens up many new vistas; however we will not pursue it further because it is beyond the scope of this book.