Elliptic Curve Addition Without Tears

[This post is based on a recent preprint of mine about addition for Edwards elliptic curves, building on work by Friedl, Bernstein, Lange, and their collaborators.]

Every math or cryptography student should know two fundamental facts about elliptic curves.

Fundamental Fact 1. The addition rule for an elliptic curve is exactly the same as the addition rule for the circle.

The addition rules are not merely similar.  They are exactly the same rule applied to different curves.

The addition of angles was already a familiar notion in Euclid, in history extending over centuries.  Today, there are many ways to describe the addition of angles of a circle: including trigonometry and multiplication of complex numbers.   Many of these descriptions are unsatisfactory, because they somehow presuppose that the circle is round, and are therefore special to the circle.

The description that I am about to give of addition of angles on the circle is one that I have never encountered before, but because it is so elementary, this construction must be well-known, even if I cannot find a reference.

circle addition
The red plus blue dots equal the purple dot.

It is best illustrated.  The red dot plus the blue dot equals the purple dot.  The sum of the red, blue, and green dots is the identity (the point at 3 o’clock on the circle).   The black dot is fixed at 9 o’clock.  The moving curve that passes through the red, blue, green, and black dots is a rectangular hyperbola, with asymptotes parallel to the coordinate axes.   The moving cross is the center of the hyperbola.  When the blue and black dots collide, the hyperbola becomes a pair of lines and the blue and black dots move to a different branch. The colored bars show the angles of the blue, red, and purple dots, confirming that red plus blue equals purple.

This is not some new addition rule on the circle.  It is the familiar clock arithmetic used to show that 2am comes four hours after 10pm (except that mathematicians add counterclockwise starting at 3 o’clock on the dial).  We just normally leave out the hyperbola.

Simple algebra shows that this construction works.    To continue, we need to set aside all other descriptions of angle addition, and accept this construction as the one true addition rule.  We apply this addition rule to an elliptic curve.  Elliptic curves can be represented in many forms.  The most usual form is called the Weierstrass form of the curve, but we prefer Edwards’s form of elliptic curves, which look like warped circles in the figures below.

Edwards curve addition
The red plus blue dots equal the purple dot

We use exactly the same addition rule for these Edwards elliptic curves (the warped circle): the red dot plus the blue dot equals the purple dot. The sum of the red, blue, and green dots is the identity (the point at 3 o’clock).  The moving curve that passes through the red, blue, green, and black dots is a rectangular hyperbola, with asymptotes parallel to the coordinate axes, as before. To add two points (red and blue), fit them to a hyperbola, and use the hyperbola to determine the green dot, which is paired with the answer (in purple).

tab1
A deformation from the circle to elliptic curves

That is all there is to it!  We have described the addition rule on elliptic curves.   It looks strange until we recognize that this is secretly how addition works for the circle too.  We illustrate the circle and elliptic curves being deformed into each other to see that the same addition rule applies to both.  Our proof of the associative law works without case splits, uniformly for the circle and elliptic curves.  We take this up in the next section.

Fundamental Fact 2. No advanced mathematics is required to prove that addition on the elliptic curve is associative.

Working with Edwards curves, the associative law can be proved using little more than polynomial division.

Typically, proofs of the associative law for elliptic curves use one or more of the following tools: intersection multiplicities, Bezout’s theorem, divisors, the Picard group, the Riemann-Roch theorem, and the Weierstrass P-function. These tools are all completely unnecessary.

The proof of associativity is given by a short  Mathematica calculation. (I used Mathematica, because that is what I use, but other computer algebra systems should work equally well.)  First, we write an explicit formula for the Edwards curve and take three points on the curve:

e[x_-,y_-]:= x^2 + y^2 - 1 - d x^2 y^2;~~ e_1 = e[x_1,y_1];~~ e_2 = e[x_2,y_2];~~ e_3 = e[x_3,y_3].

Then we create an explicit formula for addition (\oplus) using our description with the hyperbola.  The formula for addition is a rational function (ratio of polynomials) of \{x_1,y_1\} and \{x_2,y_2\} (using Mathematica’s curly braces for ordered pairs). We test for failure of the associative law by setting

\{g_1,g_2\} = (\{x_1,y_1\}\oplus\{x_2,y_2\})\oplus \{x_3,y_3\} - \{x_1,y_1\}\oplus (\{x_2,y_2\}\oplus \{x_3,y_3\})

We check associativity with the Mathematica command:

\hbox{PolynomialReduce}[\{g_1,g_2\},\{e_1,e_2,e_3\},\{x_1,y_1,x_2,y_2,x_3,y_3\}].

This command uses a naive polynomial division algorithm to show that each g_i is a combination: g_i = r_1 e_1 + r_2 e_2 + r_3 e_3.  Thus, if the three points \{x_i,y_i\} lie on the Edwards curve, then e_1 =e_2=e_3=0, so also g_i = 0.  Since the terms g_i are zero, which occurs exactly when associativity holds, we have proved the associative law for affine Edwards curves.

We might worry that the denominators that appear in the formulas for the addition rule or in g_i might sometimes be zero, causing exceptions that we are glossing over.  However, the beauty of affine Edwards curves is that even though formulas have denominators, these denominators never vanish (on the rational points of the Edwards curve) provided the constant d appearing in the formula for the Edwards curve is not a nonzero square.  (This fact can also be easily checked using Mathematica’s PolynomialReduce.)  As a bonus, these lines of Mathematica code also cover the case of a circle (d=0) as a special case. In summary, we can really verify the associative law with a few simple lines of Mathematica!

Projective Curves

grr
Inversion swaps one red dot with the other

The preprint also handles the case of projective Edwards curves (which corresponds to d a nonzero square).    An automorphism of the curve, called inversion, swaps one red dot with the other.  Inversion sends the four blue dots to the four points at infinity (which can be identified with the four dashed asymptotes).   The projective curve is covered by two copies of the affine Edwards curve that are glued together using this inversion.   We conveniently represent points on the projective curve as pairs (P,i), where P is a point on copy i of the affine curve. The formula for inversion is simply

(P,i) \mapsto (P,i+1 \mod 2).

The addition rule on the projective curve takes a very simple form

(P,i)+(Q,j) = (P\oplus Q,i+j \mod 2),

where P\oplus Q is addition on the affine curve, using the hyperbola as before. Using this formula to reduce verifications to the affine chart, the general associativity proof (in characteristic different from two) can again be verified by simple polynomial division in Mathematica.

Acknowledgements and References

This work was motivated by the need for a simple proof of the group axioms on elliptic curves for an undergraduate course in cryptography I was teaching.  Edwards curves are known to avoid the exceptional cases that Weierstrass curves encounter, so it was natural to ask whether the proof of the associative law for Edwards curves also avoids exceptional cases.

We have interchanged the x and y coordinates on the Edwards curve to make the addition rule compatible with addition on the circle.

Friedl was the first to use a computer algebra system to prove the associative law of addition for elliptic curves.  He worked with the Weierstrass form of the curve, which needlessly complicates the calculations.

The properties of Edwards curves have been extensively documented in a series of papers by Bernstein, Lange, et al.  We have simplified some of their formulas.   Bernstein and Lange motivated elliptic curves addition by analogy with the circle in a presentation to the 31st CCC in 2014.  Arene, Lange, et al. were the first to introduce hyperbolic addition on elliptic curves. I found that the same rule works for the circle after reading their article.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s