MPHELL  5.0.0
Edwards elliptic curves

Let $ E_{Ed}: a x^2 + y^2 = 1 + d x^2 y^2 $ be a twisted Edwards elliptic curve under affine coordinates. Under Projective coordinates $ E_{Ed} $ becomes $ (a X^2 + Y^2) Z^2 = Z^4 + d X^2 Y^2$. The triplet $(X, Y, Z)$ represents the affine point $(X / Z, Y / Z)$.

Under Jacobian coordinates $ E_{Ed} $ becomes $ (aX^2 Z^6 + Y^2 Z^4) = Z^{10} + d X^2 Y^2 $. The triplet $(X, Y, Z)$ represents the affine point $(X / Z^2, Y / Z^3)$.

Under Extended twisted Edwards coordinates $ E_{Ed} $ becomes $ (a X^2 + Y^2) Z^2 = Z^4 + d X^2 Y^2 $. The quadruplet $(X, Y, T, Z)$ represents the affine point $(X / Z, Y / Z)$, the auxiliary coordinate T has the property $T=X \times Y/Z$.

Edwards elliptic curves are twisted Edwards elliptic curves with $ a=1 $ so we work here with Twisted Edwards elliptic curves.

Projective Coordinates

Let

  1. P1 = (X1,Y1,Z1)
  2. P2 = (X2,Y2,Z2)

Addition

The point P3 = (X3,Y3,Z3) = P1 + P2 is given by

  1. $ A = Z1 \times Z2 $
  2. $ B = A^2; C = X1 \times X2; D = Y1 \times Y2 $
  3. $ E = d \times C \times D $
  4. $ F = B - E $
  5. $ G = B + E $
  6. $ X3 = A \times F \times [(X1 + Y1) \times (X2 + Y2) - C - D] $
  7. $ Y3 = A \times G \times (D - a \times C); Z3 = F \times G $

using 10 multiplications, 1 square, 1 times a, 1 times d, 7 additions .

This formula is taken from [BBL+08, §6] Twisted edwards curves by Daniel. J. Bernstein, Peter Birkner, Marc Joye, Tanja Lange, and Christiane Peters (2008, June) published in International Conference on Cryptology in Africa (pp. 389-405). Springer, Berlin, Heidelberg viewable at this adress https://link.springer.com/

This formula can be viewed on this website http://www.hyperelliptic.org where it is called "add-2008-bbjlp".

It is important to notice that this formula for addition is strongly unified.

Doubling

The point P3 = (X3,Y3,Z3) = 2 P1 is given by

  1. $ B = (X1 + Y1)^2; C=X1^2; D=Y1^2 $
  2. $ E = a \times C; $
  3. $ F = E + D; H = Z1^2; $
  4. $ J = F - 2 \times H $
  5. $ X3 = (B - C- D) \times J; Y3 = F \times (E - D); Z3 = F \times J $

using 3 multiplications, 4 squares, 1 times a, 6 additions, 1 times 2 .

This formula is taken from [BBL+08, §6] Twisted edwards curves by Daniel. J. Bernstein, Peter Birkner, Marc Joye, Tanja Lange, and Christiane Peters (2008, June) published in International Conference on Cryptology in Africa (pp. 389-405). Springer, Berlin, Heidelberg viewable at this adress https://link.springer.com/

This formula can be viewed on this website http://www.hyperelliptic.org where it is called "dbl-2008-bbjlp".

Extended twisted Edwards Coordinates

$ E_{Ed} $ becomes $ (a X^2 + Y^2) Z^2 = Z^4 + d X^2 Y^2 $.

Let

  1. P1 = (X1,Y1,T1,Z1)
  2. P2 = (X2,Y2,T2,Z2)

Addition

This formula is taken from [HWCD08, §3.2] Twisted Edwards Curves Revisited by Hisil, Wong, Carter and Dawson published in Asiacrypt volume 5350, pages 326-343 viewable at this adress https://link.springer.com/ .

The point P3 = (X3,Y3,T3,Z3) = P1 + P2 is given by

  1. $ A = X1 \times X2 $
  2. $ B = Y1 \times Y2 $
  3. $ C = Z1 \times T2 $
  4. $ D = T1 \times Z2 $
  5. $ E = D + C $
  6. $ F = (X1 - Y1) \times (X2 + Y2) + B - A $
  7. $ G = B + a \times A $
  8. $ H = D - C $
  9. $ X3 = E \times F $
  10. $ Y3 = G \times H $
  11. $ T3 = E \times H $
  12. $ Z3 = F \times G $

using 9 multiplications, 1 times a and 7 additions.

One can notice that those formulas are independant of the curve constant d.

This formula can be viewed on the website http://www.hyperelliptic.org and is called "add-2008-hwcd-2"

Doubling

This formula is taken from [HWCD08, §3.3] Twisted Edwards Curves Revisited by Hisil, Wong, Carter and Dawson published in Asiacrypt volume 5350, pages 326-343 viewable at this adress https://link.springer.com/ .

The point P3 = (X3,Y3,T3,Z3) = P1 + P1 is given by

  1. $ A = X1^2 $
  2. $ B = Y1^2 $
  3. $ C = 2 \times Z1^2 $
  4. $ D = a \times A $
  5. $ E = (X1 + Y1)^2 - A -B $
  6. $ G = D + B $
  7. $ F = G - C $
  8. $ H = D - B $
  9. $ X3 = E \times F $
  10. $ Y3 = G \times H $
  11. $ T3 = E \times H $
  12. $ Z3 = F \times G $

using 4 multiplications + 4 squares + 1 times a constant 6 additions and 1 doubling.

This formula can be viewed on the website http://www.hyperelliptic.org and is called "dbl-2008-hwcd"

Unified Addition

This formula is taken from [HWCD08, §3.1] Twisted Edwards Curves Revisited by Hisil, Wong, Carter and Dawson published in Asiacrypt volume 5350, pages 326-343 viewable at this adress https://link.springer.com/ .

The point P3 = (X3,Y3,T3,Z3) = P1 + P2 is given by

  1. $ A = X1 \times X2 $
  2. $ B = Y1 \times Y2 $
  3. $ C = d \times T1 \times T2 $
  4. $ D = Z1 \times Z2 $
  5. $ E = (X1 + Y1) \times (X2 + Y2) - A - B $
  6. $ F = D - C $
  7. $ G = D + C $
  8. $ H = B - aA $
  9. $ X3 = E \times F $
  10. $ Y3 = G \times H $
  11. $ T3 = E \times H $
  12. $ Z3 = F \times G $

using 9 multiplications,1 times a, 1 times d and 7 additions.

This formula can be viewed on the website http://www.hyperelliptic.org and is called "add-2008-hwcd"