Ordinary genus-1 curves over binary fields

Short Weierstrass curves

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

Lopez-Dahab coordinates with a2=0 [database entry] make the additional assumptions

a2=0and represent x y as X Y Z satisfying the following equations:

x=X/Z y=Y/Z^^{2}

- 13M for addition: 13M+4S.
- 8M for addition with Z2=1: 8M+5S.
- 5M for addition with Z1=1 and Z2=1: 5M+3S.
- 13M for readdition: 13M+3S after 13M+4S.
- 8M for readdition with Z2=1: 8M+5S after 8M+5S.
- 5M for readdition with Z1=1 and Z2=1: 5M+3S after 5M+3S.
- 3M for doubling: 3M+5S. 3M+5S.
- 1M for doubling with Z1=1: 1M+3S.

- 13.8M for addition: 13M+4S.
- 9M for addition with Z2=1: 8M+5S.
- 5.6M for addition with Z1=1 and Z2=1: 5M+3S.
- 13.6M for readdition: 13M+3S after 13M+4S.
- 9M for readdition with Z2=1: 8M+5S after 8M+5S.
- 5.6M for readdition with Z1=1 and Z2=1: 5M+3S after 5M+3S.
- 4M for doubling: 3M+5S. 3M+5S.
- 1.6M for doubling with Z1=1: 1M+3S.

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

addition | Z1=1 and Z2=1 | 5M + 3S + 1*a2 | 5M + 3S + 1*a2 |

addition | Z2=1 | 8M + 5S + 1*a2 | 8M + 5S + 1*a2 |

addition | 13M + 4S | 13M + 3S | |

doubling | Z1=1 | 1M + 3S + 1*a2 + 1*a6 | |

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

doubling | 3M + 5S + 1*a2 + 1*a6 | ||

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

- Assumptions: Z1=1 and Z2=1.
- Cost: 5M + 3S + 1*a2 + 9add.
- Cost: 5M + 3S + 1*a2 + 8add dependent upon the first point.
- Source: 2005 Doche–Lange.
- Explicit formulas:
A = Y1+Y2 B = X1+X2 Z3 = B^

^{2}D = X2*Z3 X3 = A^^{2}+B*(A+Z3+a2*B) Y3 = (D+X3)*(A*B+Z3)+(Y2+X2)*Z3^^{2}

- Assumptions: Z2=1.
- Cost: 8M + 5S + 1*a2 + 9add.
- Cost: 8M + 5S + 1*a2 + 8add dependent upon the first point.
- Source: 2005 Doche–Lange / Al-Daoud et al 2002.
- Explicit formulas:
A = Y1+Y2*Z1^

^{2}B = X1+X2*Z1 C = B*Z1 Z3 = C^^{2}D = X2*Z3 X3 = A^^{2}+C*(A+B^^{2}+a2*C) Y3 = (D+X3)*(A*C+Z3)+(Y2+X2)*Z3^^{2}

- Cost: 13M + 4S + 9add.
- Cost: 13M + 3S + 9add dependent upon the first point.
- Source: 2005 Doche–Lange / Higuchi Takagi.
- Explicit formulas:
A = X1*Z2 B = X2*Z1 C = A^

^{2}D = B^^{2}E = A+B F = C+D G = Y1*Z2^^{2}H = Y2*Z1^^{2}I = G+H J = I*E Z3 = F*Z1*Z2 X3 = A*(H+D)+B*(C+G) Y3 = (A*J+F*G)*F+(J+Z3)*X3

- Assumptions: Z1=1.
- Cost: 1M + 3S + 1*a2 + 1*a6 + 4add.
- Source: 2005 Doche–Lange.
- Explicit formulas:
C = X1^

^{2}Z3 = C X3 = C^^{2}+a6 Y3 = (Y1^^{2}+a2*Z3+a6)*X3+a6*Z3

- Assumptions: sqrta6^
^{2}=a6. - Cost: 3M + 5S + 1*sqrta6 + 4add.
- Source: 2005 Doche–Lange, following Lopez-Dahab.
- Explicit formulas:
A = X1^

^{2}B = sqrta6*Z1^^{2}C = X1*Z1 Z3 = C^^{2}X3 = (A+B)^^{2}Y3 = (B*C+(Y1+B)*(A+B))^^{2}

- Cost: 3M + 5S + 1*a2 + 1*a6 + 4add.
- Source: 2005 Doche–Lange, following Lopez-Dahab 1998.
- Explicit formulas:
A = Z1^

^{2}B = a6*A^^{2}C = X1^^{2}Z3 = A*C X3 = C^^{2}+B Y3 = (Y1^^{2}+a2*Z3+B)*X3+Z3*B

- Cost: 4M + 4S + 1*a2 + 5add.
- Source: 2005 Lange.
- Explicit formulas:
A = X1*Z1 B = X1^

^{2}C = B+Y1 D = A*C Z3 = A^^{2}X3 = C^^{2}+D+a2*Z3 Y3 = (Z3+D)*X3+B^^{2}*Z3