Explicit-Formulas Database
Genus-1 curves over large-characteristic fields
Montgomery curves EFD / Genus-1 large-characteristic / XZ coordinates for Montgomery curves

XZ coordinates for Montgomery curves

An elliptic curve in Montgomery form [more information] has parameters a b and coordinates x y satisfying the following equations:

  b*y^²=x^³+a*x^²+x

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=100M, S=1M, *param=0M, add=0M, *const=0M:

4M for doubling: 2M+2S.
3M for doubling with Z1=1: 1M+2S.
6M for differential addition: 4M+2S.
5M for differential addition with Z1=1: 3M+2S.
10M for differential addition and doubling: 6M+4S.
9M for differential addition and doubling with Z1=1: 5M+4S.
101M for scaling: 1I+1M.

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

3.6M for doubling: 2M+2S.
2.6M for doubling with Z1=1: 1M+2S.
5.6M for differential addition: 4M+2S.
4.6M for differential addition with Z1=1: 3M+2S.
9.2M for differential addition and doubling: 6M+4S.
8.2M for differential addition and doubling with Z1=1: 5M+4S.
101M for scaling: 1I+1M.

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

3.34M for doubling: 2M+2S.
2.34M for doubling with Z1=1: 1M+2S.
5.34M for differential addition: 4M+2S.
4.34M for differential addition with Z1=1: 3M+2S.
8.68M for differential addition and doubling: 6M+4S.
7.68M for differential addition and doubling with Z1=1: 5M+4S.
101M for scaling: 1I+1M.

Summary of all explicit formulas

Operation	Assumptions	Cost
doubling	Z1=1	1M + 2S + 1*a
doubling	4*a24=a+2	2M + 2S + 1*a24
doubling	4*a24=a+2	4M + 3S + 1*a24
doubling		3M + 5S + 1*a
diffadd	Z1=1	3M + 2S
diffadd		4M + 2S
diffadd		6M + 2S
diffadd		6M + 2S
ladder	Z1=1 and 4*a24=a+2	5M + 4S + 1*a24
ladder	4*a24=a+2	6M + 4S + 1*a24
ladder	4*a24=a+2	10M + 5S + 1*a24
ladder		9M + 7S + 1*a
scaling		1I + 1M

Explicit formulas for addition

Explicit formulas for doubling

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

Assumptions: Z1=1.
Cost: 1M + 2S + 1*a + 3add + 1*4.
Source: 1987 Montgomery "Speeding the Pollard and elliptic curve methods of factorization", page 261, fourth display, plus assumption Z1=1, plus common-subexpression elimination.

Explicit formulas:

      XX1 = X1^²
      X3 = (XX1-1)^²
      Z3 = 4*X1*(XX1+a*X1+1)

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

Assumptions: 4*a24=a+2.
Cost: 2M + 2S + 1*a24 + 4add.
Source: 1987 Montgomery "Speeding the Pollard and elliptic curve methods of factorization", page 261, sixth display, plus common-subexpression elimination.

Explicit formulas:

      A = X1+Z1
      AA = A^²
      B = X1-Z1
      BB = B^²
      C = AA-BB
      X3 = AA*BB
      Z3 = C*(BB+a24*C)

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

Assumptions: 4*a24=a+2.
Cost: 4M + 3S + 1*a24 + 4add + 2*4.
Source: 1987 Montgomery "Speeding the Pollard and elliptic curve methods of factorization", page 261, sixth display.

Explicit formulas:

      X3 = (X1+Z1)^²*(X1-Z1)^²
      Z3 = (4*X1*Z1)*((X1-Z1)^²+a24*(4*X1*Z1))

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

Cost: 3M + 5S + 1*a + 3add + 1*4.
Source: 1987 Montgomery "Speeding the Pollard and elliptic curve methods of factorization", page 261, fourth display.

Explicit formulas:

      X3 = (X1^²-Z1^²)^²
      Z3 = 4*X1*Z1*(X1^²+a*X1*Z1+Z1^²)

Explicit formulas for tripling

Explicit formulas for differential addition

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

Assumptions: Z1=1.
Cost: 3M + 2S + 6add.
Source: 1987 Montgomery "Speeding the Pollard and elliptic curve methods of factorization", page 261, fifth display, plus common-subexpression elimination, plus assumption Z1=1.

Explicit formulas:

      A = X2+Z2
      B = X2-Z2
      C = X3+Z3
      D = X3-Z3
      DA = D*A
      CB = C*B
      X5 = (DA+CB)^²
      Z5 = X1*(DA-CB)^²

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

Cost: 4M + 2S + 6add.
Source: 1987 Montgomery "Speeding the Pollard and elliptic curve methods of factorization", page 261, fifth display, plus common-subexpression elimination.

Explicit formulas:

      A = X2+Z2
      B = X2-Z2
      C = X3+Z3
      D = X3-Z3
      DA = D*A
      CB = C*B
      X5 = Z1*(DA+CB)^²
      Z5 = X1*(DA-CB)^²

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

Cost: 6M + 2S + 2add.
Source: 1987 Montgomery "Speeding the Pollard and elliptic curve methods of factorization", page 261, third display.

Explicit formulas:

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

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

Cost: 6M + 2S + 10add.
Source: 1987 Montgomery "Speeding the Pollard and elliptic curve methods of factorization", page 261, fifth display.

Explicit formulas:

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

Explicit formulas for differential addition and doubling

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

Assumptions: Z1=1 and 4*a24=a+2.
Cost: 5M + 4S + 1*a24 + 8add.
Source: 1987 Montgomery "Speeding the Pollard and elliptic curve methods of factorization", page 261, fifth and sixth displays, plus common-subexpression elimination, plus assumption Z1=1.

Explicit formulas:

      A = X2+Z2
      AA = A^²
      B = X2-Z2
      BB = B^²
      E = AA-BB
      C = X3+Z3
      D = X3-Z3
      DA = D*A
      CB = C*B
      X5 = (DA+CB)^²
      Z5 = X1*(DA-CB)^²
      X4 = AA*BB
      Z4 = E*(BB+a24*E)

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

Assumptions: 4*a24=a+2.
Cost: 6M + 4S + 1*a24 + 8add.
Source: 1987 Montgomery "Speeding the Pollard and elliptic curve methods of factorization", page 261, fifth and sixth displays, plus common-subexpression elimination.

Explicit formulas:

      A = X2+Z2
      AA = A^²
      B = X2-Z2
      BB = B^²
      E = AA-BB
      C = X3+Z3
      D = X3-Z3
      DA = D*A
      CB = C*B
      X5 = Z1*(DA+CB)^²
      Z5 = X1*(DA-CB)^²
      X4 = AA*BB
      Z4 = E*(BB+a24*E)

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

Assumptions: 4*a24=a+2.
Cost: 10M + 5S + 1*a24 + 14add + 2*4.
Source: 1987 Montgomery "Speeding the Pollard and elliptic curve methods of factorization", page 261, fifth and sixth displays.

Explicit formulas:

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

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

Cost: 9M + 7S + 1*a + 5add + 1*4.
Source: 1987 Montgomery "Speeding the Pollard and elliptic curve methods of factorization", page 261, third and fourth displays.

Explicit formulas:

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

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
```