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^2=x^3+a*x^2+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

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
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 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^2
X3 = (XX1-1)^2
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^2
B = X1-Z1
BB = B^2
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)^2*(X1-Z1)^2
Z3 = (4*X1*Z1)*((X1-Z1)^2+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^2-Z1^2)^2
Z3 = 4*X1*Z1*(X1^2+a*X1*Z1+Z1^2)
```

## 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)^2
Z5 = X1*(DA-CB)^2
```

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)^2
Z5 = X1*(DA-CB)^2
```

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)^2
Z5 = X1*(X2*Z3-Z2*X3)^2
```

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))^2
Z5 = X1*((X3-Z3)*(X2+Z2)-(X3+Z3)*(X2-Z2))^2
```

## 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^2
B = X2-Z2
BB = B^2
E = AA-BB
C = X3+Z3
D = X3-Z3
DA = D*A
CB = C*B
X5 = (DA+CB)^2
Z5 = X1*(DA-CB)^2
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^2
B = X2-Z2
BB = B^2
E = AA-BB
C = X3+Z3
D = X3-Z3
DA = D*A
CB = C*B
X5 = Z1*(DA+CB)^2
Z5 = X1*(DA-CB)^2
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))^2
Z5 = X1*((X3-Z3)*(X2+Z2)-(X3+Z3)*(X2-Z2))^2
X4 = (X2+Z2)^2*(X2-Z2)^2
Z4 = (4*X2*Z2)*((X2-Z2)^2+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)^2
Z5 = X1*(X2*Z3-Z2*X3)^2
X4 = (X2^2-Z2^2)^2
Z4 = 4*X2*Z2*(X2^2+a*X2*Z2+Z2^2)
```

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