Ordinary genus-1 curves over binary fields

Short Weierstrass curves

y^^{2}+x*y=x^^{3}+a2*x^^{2}+a6

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

x=X/Z

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

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

Operation | Assumptions | Cost | Readdition cost |
---|---|---|---|

doubling | Z1=1 | 2S | |

doubling | sqrta6^^{2}=a6 |
1M + 3S + 1*sqrta6 | |

doubling | roota6^^{4}=a6 |
1M + 3S + 1*roota6 | |

doubling | 1M + 4S + 1*a6 | ||

doubling | 1M + 1S + 2^^{4} + 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^^{2} |
5M + 4S + 1*sqrta6 | |

ladder | Z1=1 | 5M + 5S + 1*a6 | |

ladder | Z1=1 and sqrta6^^{2}=a6 |
5M + 5S + 2*sqrta6 | |

ladder | sqrta6^^{2}=a6 |
6M + 5S + 2*sqrta6 | |

ladder | a6=sqrta6^^{2} and sqrta6=roota6^^{2} |
6M + 5S + 1*roota6 + 1*sqrta6 | |

ladder | 6M + 7S + 2*a6 | ||

ladder | 8M + 6S + 2^^{4} + 2*a6 |
||

scaling | 1I + 1M |

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

^{2}X3 = Z3^^{2}+a6

- Assumptions: sqrta6^
^{2}=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^
^{2}, plus common-subexpression elimination. - Explicit formulas:
XX1 = X1^

^{2}ZZ1 = Z1^^{2}X3 = (XX1+sqrta6*ZZ1)^^{2}Z3 = XX1*ZZ1

- Assumptions: roota6^
^{4}=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^
^{4}, plus common-subexpression elimination. - Explicit formulas:
X3 = ((X1+roota6*Z1)^

^{2})^^{2}Z3 = (X1*Z1)^^{2}

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

^{2}ZZ1 = Z1^^{2}X3 = XX1^^{2}+a6*ZZ1^^{2}Z3 = XX1*ZZ1

- Cost: 1M + 1S + 2^
^{4}+ 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^

^{4}+a6*Z1^^{4}Z3 = (X1*Z1)^^{2}

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

^{2}X5 = X1*Z5+A*B

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

^{2}+a6*B^^{2}Z5 = X1*((X2+Z2)*(X3+Z3)-A-B)^^{2}

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

^{2}+a6*B^^{2}) Z5 = X1*((X2+Z2)*(X3+Z3)-A-B)^^{2}

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

^{2}*X3^^{2}+a6*Z2^^{2}*Z3^^{2}) Z5 = X1*((X2+Z2)*(X3+Z3)-X2*X3-Z2*Z3)^^{2}

- Assumptions: Z1=1 and a6=sqrta6^
^{2}. - 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^
^{2}, plus common-subexpression elimination. - Explicit formulas:
A = X2*Z3 B = X3*Z2 XX2 = X2^

^{2}ZZ2 = Z2^^{2}Z5 = (A+B)^^{2}X5 = X1*Z5+A*B X4 = (XX2+sqrta6*ZZ2)^^{2}Z4 = XX2*ZZ2

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

^{2}ZZ2 = Z2^^{2}Z5 = (A+B)^^{2}X5 = X1*Z5+A*B X4 = XX2^^{2}+a6*ZZ2^^{2}Z4 = XX2*ZZ2

- Assumptions: Z1=1 and sqrta6^
^{2}=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^
^{2}, plus common-subexpression elimination, plus Z1 = 1. - Explicit formulas:
A = X2*X3 B = Z2*Z3 XX2 = X2^

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

- Assumptions: sqrta6^
^{2}=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^
^{2}, plus common-subexpression elimination. - Explicit formulas:
A = X2*X3 B = Z2*Z3 XX2 = X2^

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

- Assumptions: a6=sqrta6^
^{2}and sqrta6=roota6^^{2}. - 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^
^{4}, plus common-subexpression elimination. - Explicit formulas:
A = X2*X3 B = Z2*Z3 X4 = ((X2+roota6*Z2)^

^{2})^^{2}Z4 = (X2*Z2)^^{2}X5 = Z1*(A+sqrta6*B)^^{2}Z5 = X1*((X2+Z2)*(X3+Z3)-A-B)^^{2}

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

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

- Cost: 8M + 6S + 2^
^{4}+ 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^

^{4}+a6*Z2^^{4}Z4 = (X2*Z2)^^{2}X5 = Z1*(X2^^{2}*X3^^{2}+a6*Z2^^{2}*Z3^^{2}) Z5 = X1*((X2+Z2)*(X3+Z3)-X2*X3-Z2*Z3)^^{2}

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