Twisted Edwards curve
Encyclopedia
In algebraic geometry
, the Twisted Edwards curves are plane models of elliptic curve
s, a generalisation of Edwards curve
s 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 a field
K which does not have 2=0 is an affine
plane curve defined by the equation:
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.
different from 2.
Let
and 
be points on the Twisted Edward curve. The equation of Twisted Edward curve is written as;
EE,a,d:
.
The sum of these points
on EE,a,d is:
The neutral element is (0,1) and the negative of
is (
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:
it is possible to add the points
and 
using the formula given above. The result is a point P3 that has coordinates:
.
Doubling of a point (x1,y1) on the curve EE,a,d is:
[2](x1,y1) = (x3,y3)
where
Example of doubling
Considering the same twisted Edwards curve given in the previous example, with a=3 and d=2, it is possible to double the point
. The point 2P1 obtained using the formula above has the following coordinates:
It is easy to see, with some little computations, that the point
belongs to the curve 
.
A point
on 
is represented as X, Y, Z, T satisfying the following equations
x=X/Z, y=Y/Z, xy=T/Z.
The coordinates of the point (X:Y:Z:T) are called the extended Twisted Edward coordinates. The identity element is represented by (0:1:1:0). The negative of a point is (-X:Y:Z:-T).
are called the inverted twisted Edwards coordinates on the curve
with 
≠0; this point to the affine one
on EE,a,d.
Bernstein and Lange introduced these inverted coordinates, for the case a=1 and observed that the coordinates save time in addition.
for Z1≠0.The point (X1:Y1:Z1) represents the affine point
(x1= X1/Y1, y1= Y1/Z1) on EE,a,d.
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
and it costs 10Multiplications + 1Squaring + 2D(multiplication by the curve parameter d) + 7 additions where the 2D are one multiplication by a and one by d.
Algorithm
2(X1:Y1:Z1)
This costs 3Multiplications+4Squarings+1D+7additions where 1D is a multiplication by a
Algorithm:
Algebraic geometry
Algebraic geometry is a branch of mathematics which combines techniques of abstract algebra, especially commutative algebra, with the language and the problems of geometry. It occupies a central place in modern mathematics and has multiple conceptual connections with such diverse fields as complex...
, the Twisted Edwards curves are plane models of elliptic curve
Elliptic curve
In mathematics, an elliptic curve is a smooth, projective algebraic curve of genus one, on which there is a specified point O. An elliptic curve is in fact an abelian variety — that is, it has a multiplication defined algebraically with respect to which it is a group — and O serves as the identity...
s, a generalisation of Edwards curve
Edwards curve
In mathematics, an Edwards curve is a new representation of elliptic curves, discovered by Harold M. Edwards in 2007. The concept of elliptic curves over finite fields is widely used in elliptic curve cryptography...
s introduced by Bernstein
Daniel J. Bernstein
Daniel Julius Bernstein is a mathematician, cryptologist, programmer, and professor of mathematics at the University of Illinois at Chicago...
et al. (2007) and named after Harold M. Edwards
Harold Edwards (mathematician)
Harold Mortimer Edwards, Jr. is an American mathematician working in number theory, algebra, and the history and philosophy of mathematics....
. Each twisted
Twists of curves
In mathematics an elliptic curve E over a field K has its quadratic twist, that is another elliptic curve which is isomorphic to E over an algebraic closure of K. In particular, an isomorphism between elliptic curves is an isogeny of degree 1, that is an invertible isogeny. Some curves have higher...
Edwards curve (as the name suggests) is a twist
Twists of curves
In mathematics an elliptic curve E over a field K has its quadratic twist, that is another elliptic curve which is isomorphic to E over an algebraic closure of K. In particular, an isomorphism between elliptic curves is an isogeny of degree 1, that is an invertible isogeny. Some curves have higher...
of an Edwards curve
Edwards curve
In mathematics, an Edwards curve is a new representation of elliptic curves, discovered by Harold M. Edwards in 2007. The concept of elliptic curves over finite fields is widely used in elliptic curve cryptography...
.
A twisted Edwards curve E E,a,d over a field
Field (mathematics)
In abstract algebra, a field is a commutative ring whose nonzero elements form a group under multiplication. As such it is an algebraic structure with notions of addition, subtraction, multiplication, and division, satisfying certain axioms...
K which does not have 2=0 is an affine
Affine
Affine may refer to:*Affine cipher, a special case of the more general substitution cipher*Affine combination, a certain kind of constrained linear combination*Affine connection, a connection on the tangent bundle of a differentiable manifold...
plane curve defined by the equation:
- E E,a,d:
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 these 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 characteristicCharacteristic (algebra)
In mathematics, the characteristic of a ring R, often denoted char, is defined to be the smallest number of times one must use the ring's multiplicative identity element in a sum to get the additive identity element ; the ring is said to have characteristic zero if this repeated sum never reaches...
different from 2.
Let
and be points on the Twisted Edward curve. The equation of Twisted Edward curve is written as;EE,a,d:
.The sum of these points
on EE,a,d is:
The neutral element is (0,1) and the negative of
is (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:
it is possible to add the points
and using the formula given above. The result is a point P3 that has coordinates:.Doubling on Twisted Edward curves
Doubling can be performed with exactly the same formula as addition.Doubling of a point (x1,y1) on the curve EE,a,d is:
[2](x1,y1) = (x3,y3)
where
Example of doubling
Considering the same twisted Edwards curve given in the previous example, with a=3 and d=2, it is possible to double the point
. The point 2P1 obtained using the formula above has the following coordinates:It is easy to see, with some little computations, that the point
belongs to the curve .Extended coordinates
There is another kind of coordinate system with which a point in the Twisted Edwards curves can be represented.A point
on is represented as X, Y, Z, T satisfying the following equationsx=X/Z, y=Y/Z, xy=T/Z.
The coordinates of the point (X:Y:Z:T) are called the extended Twisted Edward coordinates. The identity element is represented by (0:1:1:0). The negative of a point is (-X:Y:Z:-T).
Inverted Twisted Edwards Coordinates
The coordinates of the point are called the inverted twisted Edwards coordinates on the curvewith ≠0; this point to the affine one on EE,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: for Z1≠0.The point (X1:Y1:Z1) represents the affine pointAffine space
In mathematics, an affine space is a geometric structure that generalizes the affine properties of Euclidean space. In an affine space, one can subtract points to get vectors, or add a vector to a point to get another point, but one cannot add points. In particular, there is no distinguished point...
(x1= X1/Y1, y1= Y1/Z1) on EE,a,d.
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
Addition in Projective Twisted curves
The addition on a projective twisted Edwards curve is given by: (X1:Y1:Z1)+(X2:Y2:Z2)and it costs 10Multiplications + 1Squaring + 2D(multiplication by the curve parameter d) + 7 additions where the 2D are one multiplication by a and one by d.
Algorithm
- A= Z1.Z2,
- B=A2
- C=X1.X2
- D=Y1.Y2
- E=dC.D
- F=B-E
- G=B+E
- X3= A.F((X1+Y1).(X2+Y2)-C-D
- Y3=A.G.(D-aC)
- Z3=F.G
2(X1:Y1:Z1)
This costs 3Multiplications+4Squarings+1D+7additions where 1D is a multiplication by a
Algorithm:
- B=(X1+Y1)2
- C= X12
- D=Y12
- E=aC
- F= E+D
- H=Z12
- J=F-2H
- X3=(B-C-D).J
- Y3=F.(E-D)
- Z3= F.J
See also
- For more information about the running-time required in a specific case, see Table of costs of operations in elliptic curvesTable of costs of operations in elliptic curvesThis table relates to the computational cost for certain operations used in elliptic curve cryptography, used in practice for strong cryptographic security of a public key system. The columns of the table are labelled by various computational steps...
.
External links
- http://hyperelliptic.org/EFD/g1p/index.html
- http://hyperelliptic.org/EFD/g1p/auto-twisted.html