Edwards coordinates for elliptic curves

This is joint work of Daniel J. Bernstein and Tanja Lange, building on work by Harold M. Edwards.

Summary of results

Fix a non-binary field k. If c,d are in k and cd(1-dc^4) is nonzero then the Edwards curve x^2+y^2 = c^2(1+dx^2y^2) is birationally equivalent to an elliptic curve. If k is finite then a sizeable fraction of all elliptic curves over k can be written as Edwards curves; many Edwards curves are isomorphic to Edwards curves with d=1; all Edwards curves are isomorphic to Edwards curves with c=1.

If d is not a square in k then the affine points (x,y) on the Edwards curve form a group under the binary operation (x1,y1), (x2,y2) |-> ((x1y2+x2y1)/c(1+dx1x2y1y2),(y1y2-x1x2)/c(1-dx1x2y1y2)). The neutral element of the group is (0,c). The opposite of (x,y) in the group is (-x,y). This group is isomorphic to the group of points of the corresponding elliptic curve. If d is a square in k then the same operation can have exceptional points where it is not defined, but it still corresponds to elliptic-curve addition when it is defined.

Streamlined inversion-free addition formulas for projective Edwards coordinates use 10M+1S+1C+1D+7A. Here M denotes generic multiplications, S denotes squarings, C denotes multiplications by c, D denotes multiplications by d, and A denotes additions. If d is not a square then these formulas are complete: they work for all pairs of input points. Streamlined mixed addition formulas use 9M+1S+1C+1D+7A. Streamlined inversion-free doubling formulas use 3M+4S+3C+6A.

The Explicit-Formulas Database includes Magma scripts verifying elliptic-curve formulas for various coordinate systems. In particular, the Edwards page of the Explicit-Formulas Database verifies the consistency (for generic parameters c,d,e with e = 1-dc^4) of

It also verifies the consistency of Feel free to copy the formulas and use them in your own elliptic-curve computations!

Inverted Edwards coordinates provide even faster additions, only 9M + 1S + 1D + 7add, assuming c=1.

Papers

Here's the paper that introduced Edwards curves and affine Edwards coordinates: Here's our paper presenting fast explicit addition formulas for projective Edwards coordinates and analyzing the impact of Edwards curves on elliptic-curve computations, specifically elliptic-curve cryptography: Here's our paper presenting fast explicit addition formulas for inverted Edwards coordinates:

Talks

Our introduction to this topic was a talk "Addition on elliptic curves" by Harold M. Edwards at the "Mathematics: Algorithms and Proofs" workshop at the Lorentz Center at Leiden University in January 2007. Here's the abstract of the talk:
The addition operation on an elliptic curve (with a base point) is normally described today geometrically in terms of lines intersecting a nonsingular cubic. The algebraic formulas for this operation are cumbersome. Euler's very first paper on elliptic functions indicated a simple explicit formula for the addition operation on the specific elliptic curve y^2 = x^4 - 1, and Gauss's posthumous papers include essentially the same formula. The talk will show that a generalization of Euler's (and Gauss's) formula applies to arbitrary elliptic curves, giving a more algorithmic description of the addition and a clear explanation of the j-invariant of an elliptic curve.

We've spoken about Edwards coordinates in several talks since then:

Acknowledgments

We thank Harold M. Edwards for his comments and encouragement, and of course for finding the Edwards addition law in the first place. We thank Marc Joye for suggesting using the curve equation to accelerate the computation of the x-coordinate of 2P.