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 nonbinary field k.
If c,d are in k
and cd(1dc^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),(y1y2x1x2)/c(1dx1x2y1y2)).
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 ellipticcurve addition when it is defined.
Streamlined inversionfree 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 inversionfree doubling formulas use 3M+4S+3C+6A.
The
ExplicitFormulas Database
includes Magma scripts verifying ellipticcurve formulas
for various coordinate systems.
In particular,
the
Edwards page
of the ExplicitFormulas Database
verifies the consistency
(for generic parameters c,d,e with e = 1dc^4) of
 the standard addition formulas for the elliptic curve (1/e) v^2 = u^3 + (4/e2)u^2 + u,
 the Edwards addition formulas for the Edwards curve x^2 + y^2 = c^2(1 + dx^2y^2),
 streamlined 10M + 1S + 1C + 1D + 7A formulas,
and
 streamlined 10M + 1S + 1C + 1D + 7A twotemporaryregister operations.
It also verifies the consistency of
 the standard doubling formulas for the elliptic curve (1/e) v^2 = u^3 + (4/e2)u^2 + u,
 the Edwards addition formulas for the Edwards curve x^2 + y^2 = c^2(1 + dx^2y^2),
 streamlined 10M + 1S + 1C + 1D + 7A formulas,
 streamlined 10M + 1S + 1C + 1D + 7A twotemporaryregister operations,
 streamlined 3M + 4S + 3C + 6A formulas,
 streamlined 3M + 4S + 3C + 6A twotemporaryregister operations,
and
 streamlined 3M + 4S + 3C + 7A onetemporaryregister operations.
Feel free to copy the formulas and use them in your own ellipticcurve 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 ellipticcurve computations,
specifically ellipticcurve cryptography:

[newelliptic]
20pp.
(PDF)
2007.09.06.
D. J. Bernstein, Tanja Lange.
Faster addition and doubling on elliptic curves.
Asiacrypt 2007, to appear.
URL: http://cr.yp.to/papers.html#newelliptic.
Supersedes:
(PDF)
2007.04.10.
Performance evaluation of a new sidechannelresistant coordinate system for elliptic curves.
(PDF)
2007.05.22.
Performance evaluation of a new coordinate system for elliptic curves.
(PDF)
2007.07.16.
Faster addition and doubling on elliptic curves.
Here's our paper presenting fast explicit addition formulas for inverted Edwards coordinates:

[inverted]
8pp.
(PDF)
2007.10.09.
D. J. Bernstein, Tanja Lange.
Inverted Edwards coordinates.
17th Applied Algebra, Algebraic Algorithms, and Error Correcting Codes Symposium (AAECC 2007), to appear.
URL: http://cr.yp.to/papers.html#inverted.
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 jinvariant of an elliptic curve.
We've spoken about Edwards coordinates in several talks since then:
 2007.04.15, Tanja Lange, "Unified addition formulae for elliptic curves."
Slides online at
http://www.hyperelliptic.org/tanja/.
 2007.05.08, Tanja Lange, "Fast scalar multiplication on elliptic curves."
Slides online at
http://www.hyperelliptic.org/tanja/.
 2007.05.22, D. J. Bernstein and Tanja Lange, "Elliptic vs. hyperelliptic, part 3: Elliptic strikes back."
Slides online at
http://cr.yp.to/talks.html#2007.05.22.
 2007.05.28, Tanja Lange, "Sidechannel attacks and countermeasures for curve based cryptography."
Slides online at
http://www.hyperelliptic.org/tanja/.
 2007.06.07, D. J. Bernstein, "Edwards coordinates for elliptic curves."
Slides online at
http://cr.yp.to/talks.html#2007.06.07.
 2007.06.11, D. J. Bernstein and Tanja Lange, "Elliptic vs. hyperelliptic, part 3: Elliptic strikes back."
http://cr.yp.to/talks.html#2007.06.112.
 2007.07.12, Tanja Lange, "Fast scalar multiplication on elliptic curves."
Slides online at
http://www.hyperelliptic.org/tanja/.
 2007.08.16, D. J. Bernstein, "Edwards coordinates for elliptic curves."
http://cr.yp.to/talks.html#2007.08.16.
 2007.09.07, D. J. Bernstein and Tanja Lange, "Elliptic vs. hyperelliptic, part 3: Elliptic strikes back."
http://cr.yp.to/talks.html#2007.09.07.
 2007.09.10, D. J. Bernstein, "Edwards curves."
http://cr.yp.to/talks.html#2007.09.102.
 2007.10.05, Tanja Lange, "Edwards curves for cryptography."
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 xcoordinate of 2P.