Bibliography

• David V. Chudnovsky, Gregory V. Chudnovsky. "Sequences of numbers generated by addition in formal groups and new primality and factorization tests." Advances in Applied Mathematics 7 (1986), 385-434. MR 88h:11094.

  Contains formulas and operation counts for several representations of elliptic-curve points: projective coordinates on short Weierstrass curves, Jacobian coordinates on short Weierstrass curves, projective coordinates on Jacobi intersections, and projective coordinates on Hessian curves. Also contains formulas for projective coordinates on Jacobi quartics with the neutral element at infinity.

  For Jacobi-intersection addition, reports "17 multiplications, including one multiplication by a constant." For Jacobi-intersection doubling, reports 8 multiplications.

  For projective addition on short Weierstrass curves, reports "14 multiplications". For projective doubling, reports "10 multiplications." For Jacobian addition, reports 16 multiplications. For Jacobian doubling, reports 10 multiplications ("9 multiplications ... and one multiplication by a"). For Jacobian doubling with a4=-3, reports "8 multiplications."

• Peter L. Montgomery, "Speeding the Pollard and elliptic curve methods of factorization." Mathematics of Computation 48 (1987), 243-264. https://links.jstor.org/sici?sici=0025-5718(198701)48:177<243:STPAEC>2.0.CO;2-3 ISSN 0025-5718. MR 88e:11130.

  Introduces Montgomery curves and fast differential addition formulas for Montgomery curves.

• Henri Cohen, Atsuko Miyaji, Takatoshi Ono. "Efficient elliptic curve exponentiation using mixed coordinates." MR 1726152. https://www.math.u-bordeaux.fr/~cohen/asiacrypt98.dvi Pages 51-65 in: Kazuo Ohta, Dingyi Pei (editors). Advances in cryptology---ASIACRYPT '98. Lecture Notes in Computer Science 1514, Springer, 1998. ISBN 3-540-65109-8. MR 2000h:94002.

  Chudnovsky and Chudnovsky had reported speeds for addition and doubling in coordinates X:Y:Z:ZZ:ZZZ with x=X/ZZ, y=Y/ZZZ, ZZ=Z^2, ZZZ=Z^3. Cohen, Miyaji, and Ono pointed out an important improvement: if X:Y:Z is used only for a doubling and not for a general addition then there is no need to compute Z^3.

  Sometimes X:Y:Z:ZZ:ZZZ are called "Chudnovsky coordinates" or "Chudnovsky-Jacobian coordinates," and the idea of computing ZZ,ZZZ only when they are needed is called "mixing Chudnovsky coordinates with Jacobian coordinates." The EFD automatically obtains the same speedup using readditions in Jacobian coordinates.

• Daniel J. Bernstein. "A software implementation of NIST P-224." https://cr.yp.to/talks.html#2001.10.29

  Introduces S-M tradeoffs. In particular: for Jacobian doubling with a4=-3, reports 3M+5S (improving previous "4 squares, 4 mults, 8 reduces" to "5 squares, 3 mults, 7 reduces"); for Jacobian addition, reports 11M+5S ("could again trade mult for square").

• Nigel P. Smart. "The Hessian form of an elliptic curve." Pages 118-125 in: Cetin Kaya Koc, David Naccache, Christof Paar (editors). Cryptographic hardware and embedded systems---CHES 2001. Lecture Notes in Computer Science 2162, Springer, 2001. ISBN 3-540-42521-7.

  Points out that the Hessian addition formulas (dating back to Sylvester) are 3-way vectorizable.

• Pierre-Yvan Liardet, Nigel P. Smart. "Preventing SPA/DPA in ECC systems using the Jacobi form." MR 2003k:94033. Pages 391-401 in: Cetin Kaya Koc, David Naccache, Christof Paar (editors). Cryptographic hardware and embedded systems---CHES 2001. Lecture Notes in Computer Science 2162, Springer, 2001. ISBN 3-540-42521-7.

  Introduces faster algorithms for Jacobi intersections. For addition, reports "16 field multiplications." For doubling, reports "seven field multiplications."

• Marc Joye, Jean-Jacques Quisquater. "Hessian elliptic curves and side-channel attacks." https://marcjoye.github.io/publications.html MR 2003k:94032. Pages 402-410 in: Cetin Kaya Koc, David Naccache, Christof Paar (editors). Cryptographic hardware and embedded systems---CHES 2001. Lecture Notes in Computer Science 2162, Springer, 2001. ISBN 3-540-42521-7.

  Points out that the Hessian addition formulas can also be used for doublings after a permutation of input coordinates, providing a weak form of unification: specifically, 2(X1:Y1:Z1)=(Z1:X1:Y1)+(Y1:Z1:X1).

• Eric Brier, Marc Joye. "Weierstrass elliptic curves and side-channel attacks." https://marcjoye.github.io/publications.html Pages 335-345 in: David Naccache, Pascal Paillier. Public key cryptography. Lecture Notes in Computer Science 2274, Springer, 2002. ISBN 3-540-43168-3. MR 2005b:94044.

  Introduces strongly unified addition formulas for projective (and affine) coordinates on short Weierstrass curves.

• Olivier Billet, Marc Joye. "The Jacobi model of an elliptic curve and side-channel analysis." https://eprint.iacr.org/2002/125 (2002.08.22). MR 2005c:94045. Pages 34-42 in: Marc Fossorier, Tom Hoeholdt, Alain Poli (editors). Applied algebra, algebraic algorithms and error-correcting codes Lecture Notes in Computer Science 2643, Springer, 2003. ISBN 3-540-40111-3. MR 2004j:94001.

  Introduces algorithms for Jacobi quartics with the neutral element at (0,1), generally faster than the Chudnovsky formulas with the neutral element at infinity. In particular, 10M+3S+1D for addition in projective coordinates.

• Christophe Doche, Thomas Icart, David R. Kohel. "Efficient scalar multiplication by isogeny decompositions." Pages 191-206 in: Moti Yung, Yevgeniy Dodis, Aggelos Kiayias, Tal Malkin. 9th international conference on theory and practice in public-key cryptography, New York, NY, USA, April 24-26, 2006, proceedings. Lecture Notes in Computer Science 3958, Springer, 2006. ISBN 978-3-540-33851-2.

  Introduces doubling-oriented Doche-Icart-Kohel curves. Reports 3M+4S+2D for doubling. Reports 9M+3S+1D for mixed addition ("9M+3S if a multiplication by u is negligible").

  Also introduces tripling-oriented Doche-Icart-Kohel curves. Reports 4M+5S+2D for doubling ("4M+5S as long as we neglect multiplications by u, otherwise a doubling can be obtained with 6M+4S"; no explanation of the 4S). Reports 8M+3S+1D for mixed addition ("8M+3S to compute an addition. If u is a random element in the field, then an extra multiplication is required"). Reports 6M+6S+2D for tripling ("6M+6S ... a multiplication by u is negligible. Otherwise, 8M+6S are necessary").

• Daniel J. Bernstein, Tanja Lange. "Faster addition and doubling on elliptic curves." https://cr.yp.to/papers.html#newelliptic (2007.04.10, 2007.05.22, 2007.07.16, 2007.09.06); https://eprint.iacr.org/2007/286. Pages 29-50 in: Kaoru Kurosawa (editor). Advances in Cryptology: ASIACRYPT 2007. Lecture Notes in Computer Science 4833, Springer, 2007.

  Presents fast addition and doubling formulas for projective Edwards coordinates. Reports 3M+4S for doubling. Reports 10M+1S+1D for addition.

  Also reports initial construction of the EFD, with several speedups for previous coordinate systems. For doubling-oriented Doche-Icart-Kohel coordinates: reports 12M+5S+1D for addition, 8M+4S+1D for mixed addition, 2M+5S+2D for doubling. For tripling-oriented Doche-Icart-Kohel coordinates: reports 11M+6S+1D for addition, 10M+6S+1D for readdition, 7M+4S+1D for mixed addition, 2M+7S+2D for doubling. For Jacobi intersections: reports 3M+4S for doubling.

• Sylvain Duquesne. "Improving the arithmetic of elliptic curves in the Jacobi model." Submitted 2007.04.25. Information Processing Letters 104 (2007.10), 101-105.

  Introduces X,Y,Z,X^2,Z^2,X*Z coordinates for Jacobi quartics. Reports 9M+2S+1D for addition.

• Huseyin Hisil, Gary Carter, Ed Dawson. "New formulae for efficient elliptic curve arithmetic." Submitted 2007.08.20. Pages 138-151 in: Kannan Srinathan, Chandrasekaran Pandu Rangan, Moti Yung (editors). Progress in Cryptology: INDOCRYPT 2007. Lecture Notes in Computer Science 4859, Springer, 2007. ISBN 978-3-540-77025-1.

  Various speedups.

• Daniel J. Bernstein, Peter Birkner, Tanja Lange, Christiane Peters. "Optimizing double-base elliptic-curve single-scalar multiplication." Submitted 2007.08.20. https://eprint.iacr.org/2007/414 (2007.10.25); https://cr.yp.to/papers.html#doublebase (2007.10.28). Pages 167-182 in: Kannan Srinathan, Chandrasekaran Pandu Rangan, Moti Yung (editors). Progress in Cryptology: INDOCRYPT 2007. Lecture Notes in Computer Science 4859, Springer, 2007. ISBN 978-3-540-77025-1.

  Includes, among other things, a 9M+4S tripling formula for Edwards curves, and a 7M+7S tripling formula for Edwards curves. Hisil, Carter, and Dawson independently found a 9M+4S tripling formula for Edwards curves.

• Daniel J. Bernstein, Tanja Lange. "Inverted Edwards coordinates." https://cr.yp.to/papers.html#inverted (2007.10.09); https://eprint.iacr.org/2007/410 (2007.10.26). Pages 20-27 in: Serdar Boztas, Hsiao-feng Lu (editors). Applied algebra, algebraic algorithms and error-correcting codes, 17th international symposium, AAECC-17, Bangalore, India, December 16-20, 2007, proceedings. Lecture Notes in Computer Science 4851, Springer, 2007. ISBN 978-3-540-77223-1.

  Introduces inverted coordinates for Edwards curves. Reports 3M+4S+1D for doubling. Reports 9M+1S+1D for addition.

• Daniel J. Bernstein, Tanja Lange. "Analysis and optimization of elliptic-curve single-scalar multiplication." https://cr.yp.to/papers.html#efd (2007.12.04); https://eprint.iacr.org/2007/455 (2007.12.07). Proceedings of Fq8, Contemporary Mathematics, American Mathematical Society.

  Various speedups.

• Huseyin Hisil, Kenneth Wong, Gary Carter, Ed Dawson. "Faster group operations on elliptic curves." https://eprint.iacr.org/2007/441 (2008.02.25).

  Various speedups.

• Huseyin Hisil, Kenneth Wong, Gary Carter, Ed Dawson. "Twisted Edwards curves revisited." https://eprint.iacr.org/2008/522

  Various speedups.

• Joost Renes, Craig Costello, Lejla Batina. "Complete addition formulas for prime order elliptic curves." https://eprint.iacr.org/2015/1060

  Various speedups for short Weierstrass curves in projective coordinates.

The EFD also contains some corrections and speedups that cannot be found in the previous literature. Sources are indicated in the corresponding database entries.