Twisted Edwards curve

Let ${\displaystyle \mathbb {K} }$ be a field with characteristic different from 2. Let ${\displaystyle (x_{1},y_{1})}$ and ${\displaystyle (x_{2},y_{2})}$ be points on the twisted Edwards curve. The equation of twisted Edwards curve is written as;

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

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

${\displaystyle (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 ${\displaystyle (x_{1},y_{1})}$ is ${\displaystyle (-x_{1},y_{1})}$

These formulas also work for doubling. If a is a square in ${\displaystyle \mathbb {K} }$ and d is a non-square in  ${\displaystyle \mathbb {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.[3]

Example of addition

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

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

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

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

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

Doubling can be performed with exactly the same formula as addition. Doubling of a point ${\displaystyle (x_{1},y_{1})}$ on the curve E_a,d is:

${\displaystyle 2(x_{1},y_{1})=(x_{3},y_{3})}$

where

${\displaystyle {\begin{aligned}x_{3}&={\frac {x_{1}y_{1}+y_{1}x_{1}}{1+dx_{1}x_{1}y_{1}y_{1}}}={\frac {2x_{1}y_{1}}{ax_{1}^{2}+y_{1}^{2}}}\\[6pt]y_{3}&={\frac {y_{1}y_{1}-ax_{1}x_{1}}{1-dx_{1}x_{1}y_{1}y_{1}}}={\frac {y_{1}^{2}-ax_{1}^{2}}{2-ax_{1}^{2}-y_{1}^{2}}}.\end{aligned}}}$

Denominators in doubling are simplified using the curve equation ${\displaystyle dx^{2}y^{2}=ax^{2}+by^{2}-1}$. This reduces the power from 4 to 2 and allows for more efficient computation.

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 ${\displaystyle P_{1}=(1,{\sqrt {2}})}$. The point 2P₁ obtained using the formula above has the following coordinates:

${\displaystyle x_{3}={\frac {2x_{1}y_{1}}{ax_{1}^{2}+y_{1}^{2}}}={\frac {2{\sqrt {2}}}{5}},}$

${\displaystyle y_{3}={\frac {y_{1}^{2}-ax_{1}^{2}}{2-ax_{1}^{2}-y_{1}^{2}}}={\frac {1}{3}}.}$

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

The coordinates of the point ${\displaystyle (X_{1}:Y_{1}:Z_{1})}$ are called the inverted twisted Edwards coordinates on the curve ${\textstyle (X^{2}+aY^{2})Z^{2}=X^{2}Y^{2}+dZ^{4}}$with ${\textstyle X_{1}Y_{1}Z_{1}\neq 0}$; this point to the affine one ${\displaystyle (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.

The equation for the projective twisted Edwards curve is given as: ${\displaystyle (aX^{2}+Y^{2})Z^{2}=Z^{4}+dX^{2}Y^{2}}$ For Z₁ ≠ 0 the point (X₁:Y₁:Z₁) represents the affine point (x₁ = X₁/Z₁, y₁ = Y₁/Z₁) on E_E,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.

Doubling on the projective twisted curve is given by

(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[1]