The Group Structure of Elliptic Curves

In the previous discussion of elliptic curves we saw that, once we know some points on the curve, then these can be used to algebraically construct new curve points. Specifically, from two points, we take the line joining them and solve for the third point of intersection. This construction gives a binary operator. In mathematics, one of the most useful type of binary operators are those defining a group. There is a lot of mathematical theory developed for groups so, if we have a group operator, then it is important to realise this. Unfortunately, the operator defined on an elliptic curve as just described does not satisfy the requirements for a group. Specifically, it is not associative, meaning that if we combine together more than two elements then the result depends on the order of the operations. However, it turns out that, with a slight modification, the binary operator on an elliptic curve does define a group. Such groups are used in the digital signature algorithms employed by Bitcoin and other cryptocurrencies.

Recall that an elliptic curve is the solution set to a third order polynomial equation. For now let’s start with the relatively simple case where the equation is in Weierstrass normal form,

y2 = x3 + ax + b.

(1)

Here, the constant coefficients a and b lie in some base field F, as do the solutions for (x,y). In addition, there is one point at infinity 𝒪, which was required so that the binary operator is everywhere defined, and comes from the fact that we should consider algebraic curves as lying in projective space and, hence, can have points on the line at infinity. Also, it is assumed that the curve does not have singular points which, for the one given by (1), means that the cubic on the right hand side does not have a double root. This is equivalent to 4a³ + 27b² being nonzero.

As it is symmetric in y, the solutions to (1) are symmetric in reflection about the x-axis. Specifically, for a point P = (x,y) on the curve, then (x,-y) is also on the curve. I will denote this reflected point by P^r. By convention, the point at infinity is equal to its own reflection, 𝒪^r = 𝒪. As in the post on elliptic curves, I use P○Q to denote the third point of intersection of the line joining P and Q with the curve. Combining this with a reflection about the x-axis does indeed give a group operation.

Theorem 1 Let E be an elliptic curve in Weierstrass normal form, and point at infinity 𝒪. Then, it is a commutative group under the binary operator

P + Q ≡ (P○Q)r

Furthermore, the group identity is 𝒪 and the inverse of an element P is -P = P^r.

The group operator ‘+’ is as shown in figure 1 below. It is not at all obvious from looking at the plot that this operator satisfies associativity. In fact this is a rather tricky property to prove, and I go into more detail on how to prove this further below.

I previously computed explicit algebraic formulas for the binary operator on a curve in Weierstrass normal form. These can be modified by simply applying the reflection about the x-axis to obtain the equation for elliptic curve addition. Starting with two points P = (x₁, y₁) and Q = (x₂, y₂), we compute the gradient of the line joining them,

γ =

y2 – y1 x2 – x1

.

The curve sum of the points, P + Q = (x₃, y₃), is given by

x3 = γ2 – x1 – x2,

y3 = γ(x1 - x3) – y1.

In the case where the two points are equal, P = Q, the formula above for γ involves dividing by zero so, instead, we use the gradient of the curve,

γ =

dy dx

=

3x2 + a 2y

.

The formulas above apply so long as the points do not have the same x value and opposite y values, which would lead to division by zero in the formulas for γ. However, in this case, we have P = –Q, so that P + Q = 𝒪. Finally, if one or both of P and Q is the point at infinity, then addition is given simply by,

P + 𝒪 = P,

𝒪 + Q = Q.

In general, an elliptic curve is defined by a cubic polynomial, which does not have to be in Weierstrass normal form. Then, it need not be symmetric about the x-axis, and there need not be a unique point at infinity. So, addition cannot be defined by theorem 1. We can still define addition, although there is no longer a uniquely specified point to use as the group identity. Instead, we need to arbitrarily pick one point, 𝒪 and use this.

Theorem 2 Let E be an elliptic curve, and 𝒪 be any fixed element of E. Then, it is a commutative group under the binary operator

P + Q ≡ 𝒪○(P○Q).

Furthermore, the group identity is 𝒪 and the inverse of an element P is –P =(𝒪○𝒪)○P.

For an elliptic curve in Weierstrass form with 𝒪 being the point at infinity, we have 𝒪○P = P^r and 𝒪○𝒪 = 𝒪 so, in that case, the group operator specified in theorem 2 coincides with the one in theorem 1 above.

---

Examples

I previously looked at a few explicitly calculated examples of the binary operator on an elliptic curve. Now that we have instead expressed it in terms of a group operator, we can revisit these.

We look first at the curve y² = x³ + 3 over the rational numbers, starting with the point P = (1,2). We computed a point Q = P○P which, using the group notation is -2.P. So, using the calculation from the previous post,

2.P =

(

-23 16

,

-11 64

)

.

Next, we computed (-P)○Q which, using the group notation, is P – Q = 3.P. So,

3.P =

(

1873 1521

,

-130870 59319

)

.

Continuing in this way, we can in principle compute an infinite sequence of points n.P on the curve.

Next, we looked at the curve y² = x³ + 7 computed over the integers modulo the prime p = 13. We found that it is of size 7, including the point at infinity, and the 6 finite points are:

P11 = (7, 5),		P12 = (7, 8),
P21 = (8, 5),		P22 = (8, 8),
P31 = (11, 5),		P32 = (11, 8).

We also computed the binary operator on these points as,

P11○P11 = P22,

P11○P21 = P31,

P11○P31 = P21,

P11○P22 = P11,

P11○P32 = P32.

Using this together with the fact that we labelled the points so that P_i1^r = P_i2 gives the group structure,

P21 = 2.P11,

P32 = 3.P11,

P31 = 4.P11,

P22 = 5.P11,

P12 = 6.P11,

𝒪 = 7.P11,

This explicitly shows that the group is cyclic of order 7, with P₁₁ as a generator.

For the final example, we looked at the secp256k1 elliptic curve used by Bitcoin. This is defined by the equation y² = x³ + 7 over the integers modulo the 256 bit prime number,

p	=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
	= 2256 – 232 – 29 – 28 – 27 – 26 – 24 – 1.

Directly computing the group is a bit tricky. Instead, we can quickly verify the claims made in the Bitcoin wiki page. It is stated that the group is cyclic with order equal to the 256 bit prime number

q	=0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141.

This can be verified by the following steps.

1. First, check that p and q are indeed prime numbers. This is easily done in Python using the Miller–Rabin primality test.
2. Find an element P = (x,y) of the curve (other than the point at infinity). To do this, x can be chosen as a random 256 bit number and we set
   

   y = (x3 + 7)(p + 1)/4  (mod p).

   As p + 1 is a multiple of 4, a bit of modular arithmetic tells us that if x³ + 7 has a square root (mod p) then it is given by (x³ + 7)^(p + 1)/4. We then check that y² = x³ + 7 is satisfied (mod p). This has a probability of about 50% of success so, if it does not hold, we just select a different random value for x and try again. Alternatively, we can just use the generator stated in the link, as used by the Bitcoin implementation.

   x=0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798

   y=0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8

   It is easily checked that this does satisfy y² = x³ + 7 (mod p).

3. Compute q.P using the explicit formula for elliptic curve addition and the recursive formula for large exponents, and verify that it is equal to 𝒪.

This is all relatively straightforward using Python3 and, as it uses a variable length integer representation, 256 bit numbers are handled with no overflow issues. Once we verify q.P = 𝒪 in the final point, we know that P has order q. As q is prime, this means that P is of order q or 1 and, as it is not the identity, it must be of order q. Next, the size of the elliptic curve must be a multiple of q. The only way that it could fail to be cyclic of order q is if it was at least 2q in size. However, as mentioned previously, Hasse’s theorem bounds the size of the elliptic curve from above by p + 1 + 2√p, which is smaller than 2q. Hence, the elliptic curve is cyclic of prime order q as claimed, and every element of the curve (other than the point at infinity) is a generator.

---

Proof of Group Action

The fact that the group operation on an elliptic curve really does satisfy the definitions of a group, is not obvious. In fact, trying to directly prove it can get rather difficult, making the result seem very surprising.

As was noted previously, the equality P○Q = R for points P,Q,R on our elliptic curve just means that there is a line intersecting the curve at exactly these 3 points. So, it is unchanged if the order of P,Q,R is changed, giving identities,

Q○P = P○Q,

P○(P○Q) = Q.

The first of these shows that the addition law is commutative,

P + Q = 𝒪○(P○Q) = 𝒪○(Q○P) = Q + P.

The fact that 𝒪 is an additive identity is also straightforward,

𝒪 + P = 𝒪○(𝒪○P) = P.

It was also stated that the additive inverse of a point P is given by (𝒪○𝒪)○P, from which we obtain,

(-P)○P = ((𝒪○𝒪)○P)○P = 𝒪○𝒪.

Then the proof that –P is indeed an additive inverse follows,

(-P) + P = 𝒪○(𝒪○𝒪) = 𝒪.

There is only one remaining property of the addition law required for it to satisfy the definition of a group. Namely, associativity,

(P + Q) + R = P + (Q + R).

From the definition of elliptic curve addition, this is the same as the identity

(P + Q)○R = P○(Q + R)

for all points P,Q,R on the curve. In other words, if we take the line joining P + Q and R, and the line joining P and Q + R, then these should both intersect the elliptic curve at the same point. This is as in figure 2 below where, to within the accuracy of the plot, we do see that they both intersect the elliptic curve at the same point, marked in green. However, it is not clear from the plot why this should be the case, and if it really does hold for all choices of P,Q,R. In fact, it looks like a rather surprising coincidence.

It seems that this is one of those mathematical results that you come across from time to time, which are seemingly difficult to prove but, in fact there are many different methods of proof of varying levels of sophistication and technical difficulty (cf. the fundamental theorem of arithmetic). Some approaches that I am aware of are listed below.

Method 1: We can, with some perseverance, write out the general formula for addition of two points on an elliptic curve and, then, explicitly verify that it is associative. This gets very messy though, even for the simple Weierstrass normal form for which the explicit formulas were written out above. I will not even attempt this, but it can be done in principle.

Method 2: Here is a slick method, although it does require an advanced result from from algebraic geometry. The idea is that a non-constant rational function on an algebraic curve cannot be be deformed (in a rational sense) to be constant. This considers projective algebraic curves A₁, A₂, A₃ defined over an algebraically closed base field, and a rational function f:A₁×A₂ →A₃. If there exists a point Q₀ in A₂ at which f(P, Q₀) is constant in P, then f(P, Q) is constant in P for every fixed value of Q. More generally, this result holds for any complete algebraic variety A₁, connected variety A₂ and any variety A₃, but that does not matter here. This does require the base field F to be algebraically closed, but it is always possible to extend a field to an algebraically closed one, which adds points to the elliptic curve. If the result holds in this enlarged curve, then it will also hold with the original base field.

Fix a point R of our elliptic curve E and consider the map,

f(P, Q) = ((P + Q) + R) – (P + (Q + R)).

This is a rational map from E×E to E, and using the fact that 𝒪 is an additive identity, the equalities

f(P, 𝒪) = f(𝒪, Q) = 𝒪

are straightforward. So, f(P, 𝒪) = 𝒪 is constant. By the result mentioned it follows that, for each fixed Q, f(P, Q) is a constant function of P. Hence, f(P, Q) = f(𝒪, Q) = 𝒪, which completes the proof of associativity.

Method 3: Writing

S = (P + Q)○R,

T = P○(Q + R),

we need to show that S and T coincide. Note that we have the following ten points on the curve,

𝒪, P, Q, R, P○Q, Q○R, P + Q, Q + R, S, T.

Our elliptic curve can be expressed as the solutions to p(x, y, z) = 0 for points (x:y:z) in the projective plane, where p is a homogeneous cubic polynomial. Next, for points P,Q on the curve, use f_P,Q(x, y, z) = 0 for the linear equation of the line joining P and Q. This is of the form ax + by + cz and is uniquely determined up to an arbitrary rescaling of the coefficients. In the case where P and Q coincide, then we take the equation of the line tangent to the curve at P. Now, consider the three cubic equations,

p = 0,

g ≡  fP,Q fP + Q,R fQ○R,Q + R = 0,

h ≡  fQ,R fQ + R,P fP○Q,P + Q = 0.

These are all cubics in x,y,z, where p vanishes at all 10 points listed above, g vanishes at all points except possibly for T, and h vanishes at all points except possibly S.

As the curves defined by p,g intersect in exactly 9 points (counting multiplicity), and h vanishes on 8 of these, the following proposition states that it also vanishes at the 9th point S, giving S = T as required.

Proposition 3 If two projective cubic curves intersect in exactly nine points, then every cubic curve passing through eight of the points also passes through the ninth.

I won’t go into details here, but the idea is that a homogeneous cubic polynomial is a linear combination of the 10 monomials

x3, x2y, xy2, y3, x2z, xyz, y2z, xz2, yz2, z3.

If the cubic vanishes at 8 points in ‘general position’, this leaves two degrees of freedom. If two distinct cubics, g,h, intersect at these 8 points, then linear combinations of them span the entire space of cubics vanishing on these points. Any other cubic vanishing at these points will be a linear combination of g,h, so also vanishes at the 9th points. Here, ‘general position’ means that the size-10 vector of monomials at the points are linearly independent. Dealing with points not in general position does complicate things, but the result still holds.

Method 4: Another advanced method is to use the idea of the genus of an algebraic curve, which is a rational invariant. A smooth projective curve of degree d has genus (d – 1)(d – 2)/2. Curves of degree 1 and degree 2 both have genus 0, which is why we were able to parameterise degree two curves by a projective line in the earlier posts. Curves of degree 3 have genus 1, so there is no rational one-to-one and smooth map between elliptic curves and the projective line.

For points P,Q,R on the elliptic curve, using the notation of method 3 above, consider the rational function

u =

fP,Q fP + Q,R fQ○R,Q + R  fQ,R fQ + R,P fP○Q,P + Q

=

g h

.

On the elliptic curve, the zeros in the denominator cancel with the zeros in the numerator, to give a rational function defined everywhere on the curve except, in the case with S ≠ T, it can have a pole at T and has a unique zero at S. So, u gives a smooth one-to-one and, hence, invertible rational map from the elliptic curve to the projective line, contradicting the fact that the elliptic curve has a different genus from the line.