Genus-1 curves over large-characteristic fields

Montgomery curves

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

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

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

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

Operation | Assumptions | Cost | Readdition 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 |

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

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

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

- 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})

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

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

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

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

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

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

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

- 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})

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