Twisted Edwards curve

A Twisted Edwards curve of equation $10x^{2}+y^{2}=1+6x^{2}y^{2}$

---

This file may be deleted at any time.

In algebraic geometry, the Twisted Edwards curves are plane models of elliptic curves, a generalisation of Edwards curves introduced by Bernstein et al. (2007) and named after Harold M. Edwards. Each twisted Edwards curve (as the name suggests) is a twist of an Edwards curve. A twisted Edwards curve E _E,a,d over k is an affine plane curve defined by the equation:

E _E,a,d: $ax^{2}+y^{2}=1+dx^{2}y^{2}$

where a, d are distinct non-zero elements of k. An Edwards curve is a twisted Edwards curve with a = 1.

Every twisted Edward curve is birationally equivalent to an elliptic curve in Montgomery form and vice versa.

Group law

As for all elliptic curves, also for the Twisted Edwards curve it is possible to do some operations between its points, such as adding two of them or doubling (or tripling one). The results of this operations are always points that belong to the curve itself. In the following sections some formulas are given to obtain the coordinates of a point resulted from an addition between two other points (addition), or the coordinates of point resulted from a doubling of a single point on a curve.

Addition on Twisted Edward curves

let K be a field with char(k) ≠ 2. Let $(x_{1},y_{1})$ and $(x_{2},y_{2})$ be points on the Twisted Edward curve. The equation of Twisted Edward curve is written as;

E_E,a,d: $ax^{2}+y^{2}=1+dx^{2}y^{2}$.

The sum of these points $(x_{1},y_{1}),(x_{2},y_{2})$ on E_E,a,d is:

$(x_{1},y_{1})+(x_{2},y_{2})=\left({\frac {x_{1}y_{2}+y_{1}x_{2}}{1+dx_{1}x_{2}y_{1}y_{2}}},{\frac {y_{1}y_{2}-ax_{1}x_{2}}{1-dx_{1}x_{2}y_{1}y_{2}}}\right)$

The neutral element is (0,1) and the negative of $(x_{1},y_{1})$ is ($-x_{1},y_{1})$

These formulas also work for doubling. If a is a square in K and d is a non-square in K, these formulas are complete: this means that they can be used for all pairs of points without exceptions; so they work for doubling as well, and neutral elements and negatives are accepted as inputs.

Example of addition

Given the following Twisted Edwards curve with a=3 and d=2:

$3x^{2}+y^{2}=1+2x^{2}y^{2}$

it is possible to add the points $P_{1}=(1,{\sqrt {2}})$ and $P_{2}=(1,-{\sqrt {2}})$ using the formula given above. The result is a point P₃ that has coordinates:

$x_{3}={\frac {x_{1}y_{2}+y_{1}x_{2}}{1+dx_{1}x_{2}y_{1}y_{2}}}=0$

$y_{3}={\frac {y_{1}y_{2}-ax_{1}x_{2}}{1-dx_{1}x_{2}y_{1}y_{2}}}=-1$.

Doubling on Twisted Edward curves

Doubling can be performed with exactly the same formula as addition. Doubling of a point (x₁,y₁) on the curve E_E,a,d is:

[2](x₁,y₁) = (x₃,y₃)

where

$x_{3}={\frac {x_{1}y_{1}+y_{1}x_{1}}{1+dx_{1}x_{1}y_{1}y_{1}}}$

$y_{3}={\frac {y_{1}y_{1}-ax_{1}x_{1}}{1-dx_{1}x_{1}y_{1}y_{1}}}.$

Example of doubling

Considering the same Edwards curve given in the previous example, with a=3 and d=2, it is possible to double the point $P_{1}=(1,{\sqrt {2}})$. The point 2P₁ obtained using the formula above has the following coordinates:

$x_{3}={\frac {x_{1}y_{1}+y_{1}x_{1}}{1+dx_{1}x_{1}y_{1}y_{1}}}={\frac {2{\sqrt {2}}}{5}}$

$y_{3}={\frac {y_{1}y_{1}-ax_{1}x_{1}}{1-dx_{1}x_{1}y_{1}y_{1}}}={\frac {1}{3}}.$

It is easy to see, with some little computations, that the point $P_{3}=({\frac {2{\sqrt {2}}}{5}},{\frac {1}{3}})$ belongs to the curve $3x^{2}+y^{2}=1+2x^{2}y^{2}$.

Extended coordinates

There is another kind of coordinate system with which a point in the Twisted Edwards curves can be represented. A point $(x,y,z)$ on $ax^{2}+y^{2}=1+dx^{2}y^{2}$ is represented as X, Y, Z, T satisfying the following equations x=X/Z y=Y/Z xy=T/Z.

The points (X:Y:Z:T) are called the extended Twisted Edward coordinates.The identity element is represented by (0:1:1:0). The negative of these coordinates are (-X:Y:Z:-T).

Expressing an elliptic curve in twisted Edwards form saves time in arithmetic,even when the same curve can be expressed in the Edwards form. To know more about the speeds of addition and doubling in projective coordinates on Edwards curves, standard coordinates on twisted Edward curves, inverted coordinates on Edwards curves and inverted coordinates on twisted Edwards curves refer to the table in:

http://hyperelliptic.org/EFD/g1p/auto-twisted-extended-1.html

Inverted Twisted Edwards Coordinates

The points $(X_{1}:Y_{1}:Z_{1})$ are called the inverted twisted edward coordinates on the curve $(X^{2}+aY^{2})Z^{2}=X^{2}Y^{2}+dZ^{4}$with $X_{1}Y_{1}Z_{1}$≠0 and corresponds to the affine point$(Z_{1}/X_{1},Z_{1},Y_{1})$ on E_E,a,d. Bernstein and Lange introduced these inverted coordinates, for the case a=1 and observed that the coordinates save time in addition.

Projective twisted Edward coordinates

The equation for the Projective Twisted Edwards Curve is given as: $(aX^{2}+Y^{2})Z^{2}=Z^{4}+dX^{2}Y^{2}$ for Z₁≠0.The homogeneous point (X₁:Y₁:Z₁) represents the affine point (x₁= X₁/Y₁, y₁= Y₁/Z₁) on E_E,a,d. The addition and doubling formulas for this elliptic curve are defined, using the affine coordinates.

Addition in Projective Twisted curves

The addition on a projective twisted Edwards curve is given as:

(X₃:Y₃:Z₃)= (X₁:Y₁:Z₁)+(X₂:Y₂:Z₂)

and it costs 10Multiplications + 1Squaring + 2D(multiplication by the curve parameter d) + 7 additions where the 2D are one multiplcation by a and one by d.

Algorithm

A= Z₁.Z₂,

B=A²

C=X₁.X₂

D=Y₁.Y₂

E=dC.D

F=B-E

G=B+E

X₃= A.F((X₁+Y₁).(X₂+Y₂)-C-D

Y₃=A.G.(D-aC)

Z₃=F.G

Doubling on projective twisted curves

Doubling on the projective twisted curve is given as:

(X₃:Y₃:Z₃)= 2(X₁:Y₁:Z₁)

This costs 3Multiplications+4Squarings+1D+7additions where 1D is a multiplication by a

Algorithm

B=(X₁+Y₁)²

C= X₁²

D=Y₁²

E=aC

F= E+D

H=Z₁²

J=F-2H

X₃=(B-C-D).J

Y₃=F.(E-D)

Z₃= F.J

Expressing an elliptic curve in twisted Edwards form saves time in arithmetic,even when the same curve can be expressed in the Edwards form. To know more about the speeds of addition and doubling in projective coordinates on Edwards curves, standard coordinates on twisted Edward curves, inverted coordinates on Edwards curves and inverted coordinates on twisted Edwards curves refer to the table in: http://hyperelliptic.org/EFD/g1p/auto-twisted-extended-1.html

See also

• For more information about the running-time required in a specific case, see Table of costs of operations in elliptic curves.

References

• Daniel Bernstein, T.Lange, P.Birkner, C.Peters, "Twisted Edwards Curves" (PDF){{citation}}: CS1 maint: multiple names: authors list (link)

• Huseyin Hisil, Kenneth Wong, Gary Carter, Ed Dawson., "Twisted Edwards Curves revisited"{{citation}}: CS1 maint: multiple names: authors list (link)

• ECM using Edward curves Daniel J. Bernstein, Peter Birkner, Tanja Lange, and Christiane Peters

External link

• http://hyperelliptic.org/EFD/g1p/index.html
• http://hyperelliptic.org/EFD/g1p/auto-twisted.html