Elliptic Curves, Group Operator

Group Operator

A binary operator turns the points of an elliptic curve G, including ω, into an abelian group. In fact ω is the identity element. Each x3+ax+b defines its own elliptic curve, and a corresponding elliptic group.

Geometric Interpretation

Embed the curve in the xy plane, as we did in the previous section. Here is a geometric description of the group operator.

Given two points on the curve, draw the line connecting them, and extend the line until it intersects the curve in a third point. Reflect this point through the x axis, i.e. replace y with -y. This becomes the "sum" of the first two points. Clearly this operator is commutative, but is it well defined?

If the two points are reflections of each other through the x axis then the line is vertical, and does not intersect the graph in any other points. In this case we set the sum to ω. In other words, points that are reflections of each other are inverses in G.

Two points that are not reflections exhibit a well defined slope m. Write the line as y = mx+c. Substitute mx+c in y2, and move everything to one side, giving a new cubic polynomial q(x). The elliptic curve and the line intersect in at most three points, corresponding to the roots of q(x). Conversely, let x be a root of q(x) and set y = mx+c. Obviously this point is on the line. Reverse the algebra that build q, and show x,y satisfies y2 = x3+ax+b. Our points of intersection correspond to the roots of q(x).

We already have two roots in hand, the values of x corresponding to the two points we were given. Since q has two roots in the field F, it splits fully over F, and has a third root. By unique factorization in F[x], this third root is well defined. The group operator in G is well defined.

There is one case we haven't considered. In an abelian group, an element can be added to itself. How do we add a point on the curve to itself? Use calculus to draw the tangent line, find the "other" point of intersection, and reflect through the x axis. If the tangent line is vertical, set the sum to ω. See below for more details.

Formulas for the Group Operator

Start with two points p1 and p2 on the elliptic curve. We want to compute p3, the sum of p1+p2.

If p1 = ω, let p3 = p2. If p2 = ω, let p3 = p1. You can see that ω is commutative and associative with respect to G, and it's beginning to look like the identity element.

If neither summand is ω, let p1 and p2 have coordinates x1,y1 and x2,y2 respectively.

If x1 = x2 and y1 (nonzero) = -y2, let p3 = ω. This is the vertical line that crosses G in two points, reflections of each other, then extends up to infinity.

If p1 = p2, and their common y coordinate is 0, let p3 = ω. this is the tangent line that is vertical, and meets G at infinity.

With ω as group identity, each point has a unique inverse. The inverse of ω is ω, and the inverse of x,y is x,-y.

At this point p1 and p2 have different x coordinates, or they are equal with a nonzero y coordinate. We need to find the slope of the chord or tangent line.

Set m = y2-y1 over x2-x1. (This is the same if we swap p1 and p2.) If p1 = p2, set m = (3x2+a)/2y. This is the formula you would get from calculus.

For notational convenience, let j = x1 and let k = y1. The line is given by the formula y = m×(x-j)+k. This is a subspace of dimension 1 in F cross F. The same line would appear if we swapped p1 and p2. The values of j and k would change, but the subspace would remain the same. The points of intersection are the same, and the group operation remains commutative.

Substitute m×(x-j)+k in y2 and build the following polynomial.

q(x) = x3 - m2x2 + (2jm2-2km+a)x + b - j2m2 + 2jkm - k2

Since j is a root, use synthetic division to divide out x-j. The remainder is j3+aj+b-k2, which has to be 0, since j,k is a point on the elliptic curve. Replace q with the quotient as follows.

q(x) = x2 + (j-m2)x + a + jm2 + j2 -2km

Consider the tangent line first, whence m = (3j2+a)/2k. Substitute for m, clear denominators, and regroup to get this.

(x-j) × (4k2x - a2 + 8jk2 -6aj2 - 9j4)

we have another factor of x-j. The double root of q is revealed. (Yes, q can have a double root - although p cannot.) Remove this and solve for x, which will determine p3.

x3 = (9j4 + 6aj2 + a2 - 8jk2) / 4k2

x3 = m2 - 2j

With x1 = x2 = j, we may write it this way.

x3 = m2 - (x1+x2)

There is a problem when F has characteristic 2; m is not well defined. Remember, the tangent line has a 2 in the denominator. That's why the elliptic curve has a different formula when F has characteristic 2. We'll get to that later.

Next assume p1 and p2 are distinct. For notational convenience, let s = x2 and let t = y2. Recall our polynomial q(x), after x-j was factored out.

q(x) = x2 + (j-m2)x + a + jm2 + j2 -2km

With s as a root, divide through by x-s. This gives a rather bizarre remainder.

m2×(j-s) - 2km + j2 + js + s2 + a

Remember that m×(j-s) = k-t, so this becomes:

-(k+t)×m + j2 + js + s2 + a

It would be comforting to know this is 0. Plug j,k and s,t into the elliptic equation and subtract, giving this.

t2 - k2 = s3 - j3 + (s-j)a

divide through by s-j to get this.

(t+k)×m = s2 + js + j2 + a

This is the aforementioned remainder. Yes indeed, x-s is a root, and when it is factored out of q(x), the quotient is x+j+s-m2. Therefore x3 = m2-j-s, or m2-(x1+x2), which is exactly the same formula we saw earlier. It doesn't matter whether p1 and p2 are equal or distinct; p1+p2 is given by the following formula.

x3 ← m2 - (x1+x2)
-y3 ← y1 + m*(x3-x1)

The last and trickiest part is associativity. Well - not really tricky - it's just algebra - but very tedious. I'm not going to fill up five pages proving it. Other people have verified it, with the help of an algebra package on a computer. If I can think of a concise way to demonstrate associativity I'll slide it in. Meantime let's just run with it.

Closed Under Any Field

The group operator employs addition and subtraction, multiplication and division. If the operands lie in the field F, so does the result. Restrict F to a smaller subfield E, and the same elliptic currve (defined by a and b) establishes a subgroup of the original group. (This assumes a and b are contained in E.)

Under the reals, an elliptic curve builds an uncountable group. Restrict to the rationals and find a countable subgroup. The subgroup could be trivial, consisting only of ω, if the cubic equation has no rational solutions. Intermediate fields, such as the algebraic closure of Q, produce intermediate subgroups.