Ordinary genus-1 curves over binary fields

Short Weierstrass curves

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

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

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

x=X/Z y=Y/ZZ ZZ=Z^^{2}XZ=X*Z

- 14M for addition: 14M+3S.
- 9M for addition with Z2=1: 9M+4S.
- 14M for readdition: 14M+3S after 14M+3S.
- 9M for readdition with Z2=1: 9M+4S after 9M+4S.
- 2M for doubling: 2M+5S.
- 2M for doubling with Z1=1: 2M+3S. 2M+5S.

- 14.6M for addition: 14M+3S.
- 9.8M for addition with Z2=1: 9M+4S.
- 14.6M for readdition: 14M+3S after 14M+3S.
- 9.8M for readdition with Z2=1: 9M+4S after 9M+4S.
- 3M for doubling: 2M+5S.
- 2.6M for doubling with Z1=1: 2M+3S.

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

addition | Z2=1 | 9M + 4S + 1*a2 | 9M + 4S + 1*a2 |

addition | 14M + 3S | 14M + 3S | |

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

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

- Assumptions: Z2=1.
- Cost: 9M + 4S + 1*a2 + 9add.
- Cost: 9M + 4S + 1*a2 + 8add dependent upon the first point.
- Source: 2005 Doche–Lange / Al-Daoud et al 2002; modified to compute and use ZZ,XZ.
- Explicit formulas:
A = Y1+Y2*ZZ1 B = X1+X2*Z1 C = B*Z1 Z3 = C^

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

- Cost: 14M + 3S + 9add.
- Source: 2005 Doche–Lange / Higuchi Takagi; modified to compute and use ZZ,XZ.
- Explicit formulas:
A = X1*Z2 B = X2*Z1 C = A^

^{2}D = B^^{2}E = A+B F = C+D G = Y1*ZZ2 H = Y2*ZZ1 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 ZZ3 = Z3^^{2}XZ3 = X3*Z3

- Assumptions: Z1=1.
- Cost: 2M + 3S + 1*a6 + 5add.
- Source: 2008 Bernstein–Lange–Rezaeian-Farashahi "Binary Edwards Curves", plus specialization to Z1=1, plus simplification.
- Explicit formulas:
A = X1^

^{2}B = Y1^^{2}Z3 = A ZZ3 = A^^{2}X3 = ZZ3+a6 XZ3 = X3*Z3 Y3 = B*(B+X3+Z3)+a6*ZZ3+XZ3

- Assumptions: sqrta6^
^{2}=a6. - Cost: 2M + 5S + 1*a6 + 1*sqrta6 + 5add.
- Source: 2008 Bernstein–Lange–Rezaeian-Farashahi "Binary Edwards Curves".
- Explicit formulas:
A = X1^

^{2}B = Y1^^{2}Z3 = XZ1^^{2}X3 = (A+sqrta6*ZZ1)^^{2}ZZ3 = Z3^^{2}XZ3 = X3*Z3 Y3 = B*(B+X3+Z3)+a6*ZZ3+XZ3