The fastest known differential-addition formulas for elliptic curves (with small parameters) were introduced by Gaudry in 2006, beating the well-known 1987 Montgomery formulas. Computer-verified versions of Gaudry's formulas, reinterpreted as formulas for (Y:Z) and (Y^2:Z^2) coordinates on Edwards curves, have been online since June 2009 as part of the Explicit-Formulas Database: [hyperelliptic.org] [hyperelliptic.org]

One can also find slightly different Edwards (Y:Z) formulas in eprint 2008/218. I don't know any situations where 2008/218 is useful: for small parameters it's faster than 1987 Montgomery but slower than 2006 Gaudry, and for large parameters 1987 Montgomery is best.

Paper 2009/523 by Justus and Loebenberger claims to "introduce" (Y:Z) and (Y^2:Z^2) coordinates for Edwards curves. The paper cites EFD but nevertheless claims, falsely, that these coordinates are new. The central formulas in the paper are identical to previously published formulas. This is inexcusable; the paper has to be withdrawn.

---D. J. Bernstein
Research Professor, Computer Science, University of Illinois at Chicago

This is in reply to Daniel Bernstein's post from 03 November 2009.

For the first version (28 October 2009) of the paper, the authors were not aware of the works of Castryck et al. and Gaudry et al. Therefore it was regrettedly omitted to mention that Corollary 1 can also be found in the paper of Castryck, Galbraith and Farashahi "Efficient arithmetic on elliptic curves using a mixed Edwards-Montgomery representation" (eprint 2008/218, version 03 June 2008) and that the core ideas are already given in the paper of Gaudry and Lubicz "The arithmetic of characteristic 2 Kummer surfaces and of elliptic Kummer lines".

Theorem 1, of which Corollary 1 is a special case, is not in the literature. The other results, except as cited, can also not be found in the literature.

In particular our work differs in many points from the above mentioned papers:

The paper of Castryck, Galbraith and Farashahi (eprint 2008/218, version 03 June 2008) contains on page 3 the doubling formula for elliptic curves in Edwards form X^2+Y^2 = 1 + d X^2 Y^2
Y_{2n} = -(Z_n^4 + d Y_n^4) + 2Y_n^2 Z_n^2
Z_{2n} = (Z_n^4 + d Y_n^4) - 2dY_n^2 Z_n^2

In our paper one finds in Theorem 1 the doubling formula
Y_{2n} = -c^2 dY_n^4 + 2Y_n^2 Z_n^2 - c^2 Z_n^4
Z_{2n} = dY_n^4 - 2c^2dY_n^2 Z_n^2 + Z_n^4
for elliptic curves in generalized Edwards form X^2+Y^2 = c^2 (1 + d X^2 Y^2).
Further a differential addition formula for two points
Y_{m+n} = Z_{m-n}( Y_m^2 ( Z_n^2 - c^2 d Y_n^2) + Z_m^2(Y_n^2 - c^2 Z_n^2) )
Z_{m+n} = Y_{m-n}( dY_m^2 (Y_n^2 - c^2 Z_n^2) + Z_m^2(Z_n^2-c^2 d Y_n^2) ).
is given in the same theorem.

Corollary 1 in our paper looks at the formulae of Theorem 1 for c=1, obtaining for doubling
Y_{2n} = - (Y_n^2 - Z_n^2)^2 - (d-1) Y_n^4
Z_{2n} = (dY_n^2 - Z_n^2)^2 - d (d-1) Y_n^4.
Indeed one gets the same result (in a slightly different form) as given in 2008/218 by Castryck et al.

Neither the differential addition formula for c=1 nor the above mentioned formulae for elliptic curves in generalized Edwards form nor the representation (Y^2:Z^2) for points on the curve can be found in 2008/218.

In the EFD one finds on 4 March 2010 in the sections "YZ coordinates with square d for Edwards curves" and "Squared YZ coordinates with square d for Edwards curves" various formulae for differential doubling and differential addition on elliptic curves in Edwards form with c=1 for the case d is a square in the field.

In our work we never assumed that d is a square and also covered the cases when c <> 1. By doing so, we obtained formulae in both representations (Y:Z) and (Y^2:Z^2) that are slightly less efficient than those published on the EFD but hold for a broader class of curves. Also the differential tripling formulae given in our work cannot be found on EFD.

The paper of Gaudry and Lubicz "The arithmetic of characteristic 2 Kummer surfaces and of elliptic Kummer lines" and Gaudry's talk "Variants of the Montgomery form based on Theta functions" contain the basic ideas for differential addition on abelian varieties, which include in particular genus 1 curves. In their paper one finds on page 15 the following algorithm for point doubling:

Input: A point P = (x:z)
Output: The double 2P = (x':z')
x0 = (x^2+y^2)^2;
y0 = A'^2/B'^2 (x^2-y^2)^2;
x' = (x0 + y0);
y' = a/b (x0 - y0);

with A' = (a^2+b^2)/2 and B' = (a^2-b^2)/2. Also an algorithm for differential addition is presented on page 15. The operations are to be carried out on the associated Kummer variety.

Indeed our doubling and addition formulae follow with some work from the formulae provided by Gaudry et al. To obtain, however, results for (generalized) Edwards curves, one needs to specify the map from the elliptic curve in Edwards form to the associated Kummer variety explicitely. This also shows that the implications are not immediate.

We carried out in our work, focusing on elliptic curve in (generalized) Edwards form only, Gaudry's ideas much more explicitly. Also in Gaudry's work one cannot find any statement for point tripling nor formulae for recovering the x-coordinate.

According to Websters "to plagiarize" means "to steal and pass off (the ideas or words of another) as one's own".

This is here clearly not the case.

Gaudry's formulas appeared in 2006. You admit that "your" addition and doubling formulas are equivalent to Gaudry's formulas. So why haven't you withdrawn your paper?

You say that your work is "more explicit" than Gaudry's. That's absurd; Gaudry's formulas are perfectly explicit.

You say that the translation of Gaudry's formulas to Edwards form is not "immediate". Whether or not this is true, it can't save your paper: the same translation had already appeared in EFD in June 2009. (The squareness of d is orthogonal to this translation.) You can't post a paper months later that cites EFD and that claims novelty for something that had already appeared in EFD.

(You also can't post a paper months later that _doesn't_ cite EFD and that claims novelty for something that had already appeared in EFD. Ignorance is no excuse.)

You say that your formulas are for "generalized Edwards curves" x^2+y^2=c^2(1+dx^2y^2) while some previous formulas are merely for "Edwards curves" x^2+y^2=1+dx^2y^2. You're obviously missing the trivial fact that these curve shapes are equivalent: simply replace x by cx and y by cy in x^2+y^2=c^2(1+dx^2y^2) to obtain x^2+y^2=1+(dc^4)x^2y^2. Formulas for the c=1 case thus immediately produce formulas for the arbitrary-c case.

Finally, you say that your tripling formulas hadn't appeared before. Whether or not this is true, it also can't save your paper. Your paper is not titled "Tripling formulas for Edwards curves"; it is titled "Differential addition in generalized Edwards coordinates".

---D. J. Bernstein
Research Professor, Computer Science, University of Illinois at Chicago