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=1 [database entry] make the additional assumptions

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

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

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

- 13.6M for addition: 13M+3S.
- 8.8M for addition with Z2=1: 8M+4S. 8M+4S.
- 13.6M for readdition: 13M+3S after 13M+3S.
- 8.8M for readdition with Z2=1: 8M+4S after 8M+4S. 8M+4S after 8M+4S.
- 2.8M for doubling: 2M+4S.

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

addition | Z2=1 | 8M + 4S | 8M + 4S |

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

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

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

doubling | 2M + 5S + 2*a6 |

- Assumptions: Z2=1.
- Cost: 8M + 4S + 8add.
- Cost: 8M + 4S + 7add dependent upon the first point.
- Source: 2007(?) Kim–Kim "A New Method for Speeding Up Arithmetic on Elliptic Curves over Binary Fields".
- Explicit formulas:
A = X1+X2*Z1 B = Y1+Y2*ZZ1 C = A*Z1 D = C*(B+C) Z3 = C^

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

- Assumptions: Z2=1.
- Cost: 8M + 4S + 1*a2 + 9add.
- Cost: 8M + 4S + 1*a2 + 8add dependent upon the first point.
- Source: 2005 Doche–Lange / Al-Daoud et al 2002; modified to compute and use Z^
^{2}. - 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

- Cost: 13M + 3S + 9add.
- Source: 2005 Doche–Lange / Higuchi Takagi; modified to compute and use Z^
^{2}. - 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 ZZ3 = Z3^^{2}X3 = A*(H+D)+B*(C+G) Y3 = (A*J+F*G)*F+(J+Z3)*X3

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

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

- Cost: 2M + 5S + 2*a6 + 5add.
- Source: 2007(?) Kim–Kim "A New Method for Speeding Up Arithmetic on Elliptic Curves over Binary Fields".
- Explicit formulas:
A = X1^

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