Explicit-Formulas Database
Ordinary genus-1 curves over binary fields
Short Weierstrass curves EFD / Ordinary genus-1 binary / XZ coordinates for short Weierstrass curves

XZ coordinates 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

XZ coordinates [database entry] represent x y as X Z satisfying the following equations:

  x=X/Z

Best operation counts

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

1M for doubling: 1M+3S. 1M+3S. 1M+4S.
0M for doubling with Z1=1: 2S.
5M for differential addition: 5M+3S.
4M for differential addition with Z1=1: 4M+1S. 4M+3S.
6M for differential addition and doubling: 6M+5S. 6M+5S. 6M+7S.
5M for differential addition and doubling with Z1=1: 5M+4S. 5M+5S. 5M+5S.
11M for scaling: 1I+1M.

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

1.6M for doubling: 1M+3S. 1M+3S.
0.4M for doubling with Z1=1: 2S.
5.6M for differential addition: 5M+3S.
4.2M for differential addition with Z1=1: 4M+1S.
7M for differential addition and doubling: 6M+5S. 6M+5S.
5.8M for differential addition and doubling with Z1=1: 5M+4S.
11M for scaling: 1I+1M.

Summary of all explicit formulas

Operation	Assumptions	Cost
doubling	Z1=1	2S
doubling	sqrta6^²=a6	1M + 3S + 1*sqrta6
doubling	roota6^⁴=a6	1M + 3S + 1*roota6
doubling		1M + 4S + 1*a6
doubling		1M + 1S + 2^⁴ + 1*a6
diffadd	Z1=1	4M + 1S
diffadd	Z1=1	4M + 3S + 1*a6
diffadd		5M + 3S + 1*a6
diffadd		7M + 5S + 1*a6
ladder	Z1=1 and a6=sqrta6^²	5M + 4S + 1*sqrta6
ladder	Z1=1	5M + 5S + 1*a6
ladder	Z1=1 and sqrta6^²=a6	5M + 5S + 2*sqrta6
ladder	sqrta6^²=a6	6M + 5S + 2*sqrta6
ladder	a6=sqrta6^² and sqrta6=roota6^²	6M + 5S + 1roota6 + 1sqrta6
ladder		6M + 7S + 2*a6
ladder		8M + 6S + 2^⁴ + 2*a6
scaling		1I + 1M

Explicit formulas for addition

Explicit formulas for doubling

The "mdbl-2003-s" doubling formulas [database entry; Sage verification script; Sage output; three-operand code]:

Assumptions: Z1=1.
Cost: 2S + 1add.
Source: 2003 Stam "On Montgomery-like representations for elliptic curves over GF(2^k)", Section 3.2, plus a1 = 1, plus b8 = a6, plus Z1 = 1, plus common-subexpression elimination.
Explicit formulas:
```
      Z3 = X1^²
      X3 = Z3^²+a6
```

The "dbl-2003-s-3" doubling formulas [database entry; Sage verification script; Sage output; three-operand code]:

Assumptions: sqrta6^²=a6.
Cost: 1M + 3S + 1*sqrta6 + 1add.
Source: 2003 Stam "On Montgomery-like representations for elliptic curves over GF(2^k)", Section 3.2, plus a1 = 1, plus b8 = a6, plus a6 = sqrta6^², plus common-subexpression elimination.

Explicit formulas:

      XX1 = X1^²
      ZZ1 = Z1^²
      X3 = (XX1+sqrta6*ZZ1)^²
      Z3 = XX1*ZZ1

The "dbl-2003-s-4" doubling formulas [database entry; Sage verification script; Sage output; three-operand code]:

Assumptions: roota6^⁴=a6.
Cost: 1M + 3S + 1*roota6 + 1add.
Source: 2003 Stam "On Montgomery-like representations for elliptic curves over GF(2^k)", Section 3.2, plus a1 = 1, plus b8 = a6, plus a6 = roota6^⁴, plus common-subexpression elimination.

Explicit formulas:

      X3 = ((X1+roota6*Z1)^²)^²
      Z3 = (X1*Z1)^²

The "dbl-2003-s-2" doubling formulas [database entry; Sage verification script; Sage output; three-operand code]:

Cost: 1M + 4S + 1*a6 + 1add.
Source: 2003 Stam "On Montgomery-like representations for elliptic curves over GF(2^k)", Section 3.2, plus a1 = 1, plus b8 = a6, plus common-subexpression elimination.

Explicit formulas:

      XX1 = X1^²
      ZZ1 = Z1^²
      X3 = XX1^²+a6*ZZ1^²
      Z3 = XX1*ZZ1

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

Cost: 1M + 1S + 2^⁴ + 1*a6 + 1add.
Source: 2003 Stam "On Montgomery-like representations for elliptic curves over GF(2^k)", Section 3.2, plus a1 = 1, plus b8 = a6.

Explicit formulas:

      X3 = X1^⁴+a6*Z1^⁴
      Z3 = (X1*Z1)^²

Explicit formulas for tripling

Explicit formulas for differential addition

The "mdadd-2003-s" differential-addition formulas [database entry; Sage verification script; Sage output; three-operand code]:

Assumptions: Z1=1.
Cost: 4M + 1S + 2add.
Source: 2003 Stam "On Montgomery-like representations for elliptic curves over GF(2^k)", Section 3.1, plus Z1=1, plus common-subexpression elimination.

Explicit formulas:

      A = X2*Z3
      B = X3*Z2
      Z5 = (A+B)^²
      X5 = X1*Z5+A*B

The "mdadd-2003-s-2" differential-addition formulas [database entry; Sage verification script; Sage output; three-operand code]:

Assumptions: Z1=1.
Cost: 4M + 3S + 1*a6 + 5add.
Source: 2003 Stam "On Montgomery-like representations for elliptic curves over GF(2^k)", Section 3.2, plus a1 = 1, plus b8 = a6, plus common-subexpression elimination, plus Z1=1.

Explicit formulas:

      A = X2*X3
      B = Z2*Z3
      X5 = A^²+a6*B^²
      Z5 = X1*((X2+Z2)*(X3+Z3)-A-B)^²

The "dadd-2003-s-2" differential-addition formulas [database entry; Sage verification script; Sage output; three-operand code]:

Cost: 5M + 3S + 1*a6 + 5add.
Source: 2003 Stam "On Montgomery-like representations for elliptic curves over GF(2^k)", Section 3.2, plus a1 = 1, plus b8 = a6, plus common-subexpression elimination.

Explicit formulas:

      A = X2*X3
      B = Z2*Z3
      X5 = Z1*(A^²+a6*B^²)
      Z5 = X1*((X2+Z2)*(X3+Z3)-A-B)^²

The "dadd-2003-s" differential-addition formulas [database entry; Sage verification script; Sage output; three-operand code]:

Cost: 7M + 5S + 1*a6 + 5add.
Source: 2003 Stam "On Montgomery-like representations for elliptic curves over GF(2^k)", Section 3.2, plus a1 = 1, plus b8 = a6.

Explicit formulas:

      X5 = Z1*(X2^²*X3^²+a6*Z2^²*Z3^²)
      Z5 = X1*((X2+Z2)*(X3+Z3)-X2*X3-Z2*Z3)^²

Explicit formulas for differential addition and doubling

The "mladd-2003-s-2" differential-addition-and-doubling formulas [database entry; Sage verification script; Sage output; three-operand code]:

Assumptions: Z1=1 and a6=sqrta6^².
Cost: 5M + 4S + 1*sqrta6 + 3add.
Source: 2003 Stam "On Montgomery-like representations for elliptic curves over GF(2^k)", Section 3.1, plus Z1=1, plus a6 = sqrta6^², plus common-subexpression elimination.

Explicit formulas:

      A = X2*Z3
      B = X3*Z2
      XX2 = X2^²
      ZZ2 = Z2^²
      Z5 = (A+B)^²
      X5 = X1*Z5+A*B
      X4 = (XX2+sqrta6*ZZ2)^²
      Z4 = XX2*ZZ2

The "mladd-2003-s" differential-addition-and-doubling formulas [database entry; Sage verification script; Sage output; three-operand code]:

Assumptions: Z1=1.
Cost: 5M + 5S + 1*a6 + 3add.
Source: 2003 Stam "On Montgomery-like representations for elliptic curves over GF(2^k)", Section 3.1, plus Z1=1, plus common-subexpression elimination.

Explicit formulas:

      A = X2*Z3
      B = X3*Z2
      XX2 = X2^²
      ZZ2 = Z2^²
      Z5 = (A+B)^²
      X5 = X1*Z5+A*B
      X4 = XX2^²+a6*ZZ2^²
      Z4 = XX2*ZZ2

The "mladd-2003-s-3" differential-addition-and-doubling formulas [database entry; Sage verification script; Sage output; three-operand code]:

Assumptions: Z1=1 and sqrta6^²=a6.
Cost: 5M + 5S + 2*sqrta6 + 6add.
Source: 2003 Stam "On Montgomery-like representations for elliptic curves over GF(2^k)", Section 3.2, plus a1 = 1, plus b8 = a6, plus a6 = sqrta6^², plus common-subexpression elimination, plus Z1 = 1.

Explicit formulas:

      A = X2*X3
      B = Z2*Z3
      XX2 = X2^²
      ZZ2 = Z2^²
      X4 = (XX2+sqrta6*ZZ2)^²
      Z4 = XX2*ZZ2
      X5 = (A+sqrta6*B)^²
      Z5 = X1*((X2+Z2)*(X3+Z3)-A-B)^²

The "ladd-2003-s-3" differential-addition-and-doubling formulas [database entry; Sage verification script; Sage output; three-operand code]:

Assumptions: sqrta6^²=a6.
Cost: 6M + 5S + 2*sqrta6 + 6add.
Source: 2003 Stam "On Montgomery-like representations for elliptic curves over GF(2^k)", Section 3.2, plus a1 = 1, plus b8 = a6, plus a6 = sqrta6^², plus common-subexpression elimination.

Explicit formulas:

      A = X2*X3
      B = Z2*Z3
      XX2 = X2^²
      ZZ2 = Z2^²
      X4 = (XX2+sqrta6*ZZ2)^²
      Z4 = XX2*ZZ2
      X5 = Z1*(A+sqrta6*B)^²
      Z5 = X1*((X2+Z2)*(X3+Z3)-A-B)^²

The "ladd-2003-s-4" differential-addition-and-doubling formulas [database entry; Sage verification script; Sage output; three-operand code]:

Assumptions: a6=sqrta6^² and sqrta6=roota6^².
Cost: 6M + 5S + 1*roota6 + 1*sqrta6 + 6add.
Source: 2003 Stam "On Montgomery-like representations for elliptic curves over GF(2^k)", Section 3.2, plus a1 = 1, plus b8 = a6, plus a6 = roota6^⁴, plus common-subexpression elimination.

Explicit formulas:

      A = X2*X3
      B = Z2*Z3
      X4 = ((X2+roota6*Z2)^²)^²
      Z4 = (X2*Z2)^²
      X5 = Z1*(A+sqrta6*B)^²
      Z5 = X1*((X2+Z2)*(X3+Z3)-A-B)^²

The "ladd-2003-s-2" differential-addition-and-doubling formulas [database entry; Sage verification script; Sage output; three-operand code]:

Cost: 6M + 7S + 2*a6 + 6add.
Source: 2003 Stam "On Montgomery-like representations for elliptic curves over GF(2^k)", Section 3.2, plus a1 = 1, plus b8 = a6, plus common-subexpression elimination.

Explicit formulas:

      A = X2*X3
      B = Z2*Z3
      XX2 = X2^²
      ZZ2 = Z2^²
      X4 = XX2^²+a6*ZZ2^²
      Z4 = XX2*ZZ2
      X5 = Z1*(A^²+a6*B^²)
      Z5 = X1*((X2+Z2)*(X3+Z3)-A-B)^²

The "ladd-2003-s" differential-addition-and-doubling formulas [database entry; Sage verification script; Sage output; three-operand code]:

Cost: 8M + 6S + 2^⁴ + 2*a6 + 6add.
Source: 2003 Stam "On Montgomery-like representations for elliptic curves over GF(2^k)", Section 3.2, plus a1 = 1, plus b8 = a6.

Explicit formulas:

      X4 = X2^⁴+a6*Z2^⁴
      Z4 = (X2*Z2)^²
      X5 = Z1*(X2^²*X3^²+a6*Z2^²*Z3^²)
      Z5 = X1*((X2+Z2)*(X3+Z3)-X2*X3-Z2*Z3)^²

Explicit formulas for scaling

The "scale" scaling formulas [database entry; Sage verification script; Sage output; three-operand code]:

Cost: 1I + 1M + 0add.
Explicit formulas:
```
      X3 = X1/Z1
      Z3 = 1
```