Explicit-Formulas Database
Ordinary genus-1 curves over binary fields
Short Weierstrass curves EFD / Ordinary genus-1 binary / Extended Lopez-Dahab coordinates with a2=1 for short Weierstrass curves

Extended Lopez-Dahab coordinates with a2=1 for short Weierstrass curves

An elliptic curve in short Weierstrass form [more information] has parameters a2 a6 and coordinates x y satisfying the following equations:

  y^²+x*y=x^³+a2*x^²+a6

Extended Lopez-Dahab coordinates with a2=1 [database entry] make the additional assumptions

  a2=1

and represent x y as X Y Z ZZ satisfying the following equations:

  x=X/Z
  y=Y/Z^²
  ZZ=Z^²

Best operation counts

Smallest multiplication counts assuming I=10M, S=0M, *param=0M, add=0M, *const=0M:

13M for addition: 13M+3S.
8M for addition with Z2=1: 8M+4S. 8M+4S.
13M for readdition: 13M+3S after 13M+3S.
8M for readdition with Z2=1: 8M+4S after 8M+4S. 8M+4S after 8M+4S.
2M for doubling: 2M+4S. 2M+5S.

Smallest multiplication counts assuming I=10M, S=0.2M, *param=0M, add=0M, *const=0M:

13.6M for addition: 13M+3S.
8.8M for addition with Z2=1: 8M+4S. 8M+4S.
13.6M for readdition: 13M+3S after 13M+3S.
8.8M for readdition with Z2=1: 8M+4S after 8M+4S. 8M+4S after 8M+4S.
2.8M for doubling: 2M+4S.

Summary of all explicit formulas

Operation	Assumptions	Cost	Readdition cost
addition	Z2=1	8M + 4S	8M + 4S
addition	Z2=1	8M + 4S + 1*a2	8M + 4S + 1*a2
addition		13M + 3S	13M + 3S
doubling	sqrta6^²=a6	2M + 4S + 1a6 + 1sqrta6
doubling		2M + 5S + 2*a6

Explicit formulas for addition

The "madd-2007-kk" addition formulas [database entry; Sage verification script; Sage output; three-operand code]:

Assumptions: Z2=1.
Cost: 8M + 4S + 8add.
Cost: 8M + 4S + 7add dependent upon the first point.
Source: 2007(?) Kim–Kim "A New Method for Speeding Up Arithmetic on Elliptic Curves over Binary Fields".

Explicit formulas:

      A = X1+X2*Z1
      B = Y1+Y2*ZZ1
      C = A*Z1
      D = C*(B+C)
      Z3 = C^²
      ZZ3 = Z3^²
      X3 = B^²+C*A^²+D
      Y3 = (X3+X2*Z3)*D+(X2+Y2)*ZZ3

The "madd-2005-dl" addition formulas [database entry; Sage verification script; Sage output; three-operand code]:

Assumptions: Z2=1.
Cost: 8M + 4S + 1*a2 + 9add.
Cost: 8M + 4S + 1*a2 + 8add dependent upon the first point.
Source: 2005 Doche–Lange / Al-Daoud et al 2002; modified to compute and use Z^².

Explicit formulas:

      A = Y1+Y2*ZZ1
      B = X1+X2*Z1
      C = B*Z1
      Z3 = C^²
      ZZ3 = Z3^²
      D = X2*Z3
      X3 = A^²+C*(A+B^²+a2*C)
      Y3 = (D+X3)*(A*C+Z3)+(Y2+X2)*ZZ3

The "add-2005-dl" addition formulas [database entry; Sage verification script; Sage output; three-operand code]:

Cost: 13M + 3S + 9add.
Source: 2005 Doche–Lange / Higuchi Takagi; modified to compute and use Z^².

Explicit formulas:

      A = X1*Z2
      B = X2*Z1
      C = A^²
      D = B^²
      E = A+B
      F = C+D
      G = Y1*ZZ2
      H = Y2*ZZ1
      I = G+H
      J = I*E
      Z3 = F*Z1*Z2
      ZZ3 = Z3^²
      X3 = A*(H+D)+B*(C+G)
      Y3 = (A*J+F*G)*F+(J+Z3)*X3

Explicit formulas for doubling

The "dbl-2008-blr" doubling formulas [database entry; Sage verification script; Sage output; three-operand code]:

Assumptions: sqrta6^²=a6.
Cost: 2M + 4S + 1*a6 + 1*sqrta6 + 5add.
Source: 2008 Bernstein–Lange–Rezaeian-Farashahi "Binary Edwards Curves".

Explicit formulas:

      A = X1^²
      B = Y1^²
      Z3 = ZZ1*A
      ZZ3 = Z3^²
      X3 = (A+sqrta6*ZZ1)^²
      Y3 = B*(B+X3+Z3)+a6*ZZ3+ZZ3

The "dbl-2007-kk" doubling formulas [database entry; Sage verification script; Sage output; three-operand code]:

Cost: 2M + 5S + 2*a6 + 5add.
Source: 2007(?) Kim–Kim "A New Method for Speeding Up Arithmetic on Elliptic Curves over Binary Fields".

Explicit formulas:

      A = X1^²
      B = Y1^²
      Z3 = ZZ1*A
      ZZ3 = Z3^²
      X3 = A^²+a6*ZZ1^²
      Y3 = B*(B+X3+Z3)+a6*ZZ3+ZZ3

Extended Lopez-Dahab coordinates with a2=1 for short Weierstrass curves

Best operation counts

Summary of all explicit formulas

Explicit formulas for addition

Explicit formulas for doubling

Explicit formulas for tripling

Explicit formulas for differential addition

Explicit formulas for differential addition and doubling

Explicit formulas for scaling