Ordinary genus-1 curves over binary fields

Short Weierstrass curves

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

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

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

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

- 15M for addition: 14M+5S.
- 10.6M for addition with Z2=1: 10M+3S.
- 13.8M for readdition: 13M+4S after 14M+5S.
- 10.6M for readdition with Z2=1: 10M+3S after 10M+3S.
- 5M for doubling: 4M+5S.
- 1.4M for doubling with Z1=1: 1M+2S.
- 13.2M for scaling: 1I+3M+1S.

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

addition | Z2=1 | 10M + 3S + 1*a2 | 10M + 3S + 1*a2 |

addition | 14M + 5S + 1*a2 | 13M + 4S + 1*a2 | |

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

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

scaling | 1I + 3M + 1S |

- Assumptions: Z2=1.
- Cost: 10M + 3S + 1*a2 + 7add.
- Source: 2005 Doche–Lange.
- Explicit formulas:
O1 = Z1^

^{2}B = X2*O1 D = Y2*O1*Z1 E = X1+B F = Y1+D Z3 = E*Z1 H = F*X2+Z3*Y2 I = F+Z3 G = Z3^^{2}X3 = a2*G+F*I+E*E^^{2}Y3 = I*X3+G*H

- Cost: 14M + 5S + 1*a2 + 7add.
- Cost: 13M + 4S + 1*a2 + 7add dependent upon the first point.
- Source: 2005 Doche–Lange.
- Explicit formulas:
O1 = Z1^

^{2}O2 = Z2^^{2}A = X1*O2 B = X2*O1 C = Y1*O2*Z2 D = Y2*O1*Z1 E = A+B F = C+D G = E*Z1 H = F*X2+G*Y2 Z3 = G*Z2 I = F+Z3 X3 = a2*Z3^^{2}+F*I+E*E^^{2}Y3 = I*X3+G^^{2}*H

- Assumptions: Z1=1.
- Cost: 1M + 2S + 1*a6 + 5add.
- Source: 2008 Bernstein–Lange.
- Explicit formulas:
A = X1^

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

- Cost: 4M + 5S + 1*a6 + 4add.
- Source: 2005 Doche–Lange.
- Explicit formulas:
A = X1^

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

- Cost: 1I + 3M + 1S + 0add.
- Explicit formulas:
A = 1/Z1 B = A^

^{2}X3 = B*X1 Y3 = A*B*Y1 Z3 = 1