Ordinary genus-1 curves over binary fields

Binary Edwards curves

d1*(x+y)+d2*(x^^{2}+y^^{2})=(x+x^^{2})*(y+y^^{2})

WZ coordinates with d1=d2 [database entry] make the additional assumptions

d1=d2and represent x y as W Z satisfying the following equations:

x+y=W/Z

- 1M for doubling: 1M+3S. 1M+3S.
- 6M for differential addition: 6M+2S. 6M+2S.
- 5M for differential addition with Z1=1: 5M+1S.
- 7M for differential addition and doubling: 7M+4S.
- 5M for differential addition and doubling with Z1=1: 5M+4S.
- 11M for scaling: 1I+1M.

- 1.6M for doubling: 1M+3S. 1M+3S.
- 6.4M for differential addition: 6M+2S. 6M+2S.
- 5.2M for differential addition with Z1=1: 5M+1S.
- 7.8M for differential addition and doubling: 7M+4S.
- 5.8M for differential addition and doubling with Z1=1: 5M+4S.
- 11M for scaling: 1I+1M.

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

doubling | 1M + 3S + 1*d1 | ||

doubling | e^^{4}=d1 and f^^{4}=d2/d1+1 |
1M + 3S + 1*e + 1*f | |

diffadd | Z1=1 | 5M + 1S + 1*d1 | |

diffadd | e^^{2}=d1 and f^^{2}=d2/d1+1 and Z1=1 |
6M + 1S + 1*e + 1*f | |

diffadd | 6M + 2S + 2*d1 | ||

diffadd | e^^{2}=d1 and f^^{2}=d2/d1+1 |
6M + 2S + 1*d1 + 1*e + 1*f | |

diffadd | 7M + 1S + 1*d1 | ||

diffadd | e^^{2}=d1 and f^^{2}=d2/d1+1 |
8M + 1S + 1*e + 1*f | |

ladder | Z1=1 | 5M + 4S + 2*d1 | |

ladder | Z1=1 and e^^{4}=d1 and f^^{4}=d2/d1+1 and ee=e*e and ff=f*f |
6M + 4S + 1*ee + 1*ff + 1*e + 1*f | |

ladder | 7M + 4S + 2*d1 | ||

ladder | e^^{4}=d1 and f^^{4}=d2/d1+1 and ee=e*e and ff=f*f |
8M + 4S + 1*ee + 1*ff + 1*e + 1*f | |

scaling | 1I + 1M |

- Cost: 1M + 3S + 1*d1 + 2add.
- Source: 2008 Bernstein–Lange–Rezaeian Farashahi.
- Explicit formulas:
C = W1*(Z1+W1) W3 = C^

^{2}Z3 = d1*(Z1^^{2})^^{2}+W3

- Assumptions: e^
^{4}=d1 and f^^{4}=d2/d1+1. - Cost: 1M + 3S + 1*e + 1*f + 3add.
- Source: 2008 Bernstein–Lange–Rezaeian Farashahi.
- Explicit formulas:
C = W1*(Z1+W1) W3 = C^

^{2}Z3 = W3+((e*Z1+f*W1)^^{2})^^{2}

- Assumptions: Z1=1.
- Cost: 5M + 1S + 1*d1 + 4add.
- Source: 2008 Bernstein–Lange–Rezaeian Farashahi.
- Explicit formulas:
C = W2*(Z2+W2) D = W3*(Z3+W3) E = Z2*Z3 V = C*D U = V+d1*E^

^{2}W5 = V+W1*U Z5 = U

- Assumptions: e^
^{2}=d1 and f^^{2}=d2/d1+1 and Z1=1. - Cost: 6M + 1S + 1*e + 1*f + 5add.
- Source: 2008 Bernstein–Lange–Rezaeian Farashahi.
- Explicit formulas:
C = W2*(Z2+W2) D = W3*(Z3+W3) E = Z2*Z3 F = W2*W3 V = C*D U = V+(e*E+f*F)^

^{2}W5 = V+W1*U Z5 = U

- Cost: 6M + 2S + 2*d1 + 5add.
- Source: 2008 Bernstein–Lange–Rezaeian Farashahi.
- Explicit formulas:
A = W2*W3 B = Z2*Z3 C = (W2+Z2)*(W3+Z3) W5 = Z1*(d1*(C+A+B)^

^{2}) Z5 = W1*(A*C+d1*B^^{2})

- Assumptions: e^
^{2}=d1 and f^^{2}=d2/d1+1. - Cost: 6M + 2S + 1*d1 + 1*e + 1*f + 6add.
- Source: 2008 Bernstein–Lange–Rezaeian Farashahi.
- Explicit formulas:
A = W2*W3 B = Z2*Z3 C = (W2+Z2)*(W3+Z3) W5 = Z1*(d1*(C+A+B)^

^{2}) Z5 = W1*(A*C+(e*B+f*A)^^{2})

- Cost: 7M + 1S + 1*d1 + 4add.
- Source: 2008 Bernstein–Lange–Rezaeian Farashahi.
- Explicit formulas:
C = W2*(Z2+W2) D = W3*(Z3+W3) E = Z2*Z3 V = C*D U = V+d1*E^

^{2}W5 = V*Z1+U*W1 Z5 = U*Z1

- Assumptions: e^
^{2}=d1 and f^^{2}=d2/d1+1. - Cost: 8M + 1S + 1*e + 1*f + 5add.
- Source: 2008 Bernstein–Lange–Rezaeian Farashahi.
- Explicit formulas:
C = W2*(Z2+W2) D = W3*(Z3+W3) E = Z2*Z3 F = W2*W3 V = C*D U = V+(e*E+f*F)^

^{2}W5 = V*Z1+U*W1 Z5 = U*Z1

- Assumptions: Z1=1.
- Cost: 5M + 4S + 2*d1 + 5add.
- Source: 2008 Bernstein–Lange–Rezaeian Farashahi.
- Explicit formulas:
C = W2*(Z2+W2) V = C*W3*(Z3+W3) U = V+d1*(Z2*Z3)^

^{2}W4 = C^^{2}Z4 = d1*(Z2^^{2})^^{2}+W4 W5 = V+U*W1 Z5 = U

- Assumptions: Z1=1 and e^
^{4}=d1 and f^^{4}=d2/d1+1 and ee=e*e and ff=f*f. - Cost: 6M + 4S + 1*ee + 1*ff + 1*e + 1*f + 7add.
- Source: 2008 Bernstein–Lange–Rezaeian Farashahi.
- Explicit formulas:
C = W2*(Z2+W2) D = W3*(Z3+W3) W4 = C^

^{2}Z4 = W4+((e*Z2+f*W2)^^{2})^^{2}E = Z2*Z3 F = W2*W3 V = C*D U = V+(ee*E+ff*F)^^{2}W5 = V+U*W1 Z5 = U

- Cost: 7M + 4S + 2*d1 + 5add.
- Source: 2008 Bernstein–Lange–Rezaeian Farashahi.
- Explicit formulas:
C = W2*(Z2+W2) V = C*W3*(Z3+W3) U = V+d1*(Z2*Z3)^

^{2}W4 = C^^{2}Z4 = d1*(Z2^^{2})^^{2}+W4 W5 = V*Z1+U*W1 Z5 = U*Z1

- Assumptions: e^
^{4}=d1 and f^^{4}=d2/d1+1 and ee=e*e and ff=f*f. - Cost: 8M + 4S + 1*ee + 1*ff + 1*e + 1*f + 7add.
- Source: 2008 Bernstein–Lange–Rezaeian Farashahi.
- Explicit formulas:
C = W2*(Z2+W2) D = W3*(Z3+W3) W4 = C^

^{2}Z4 = W4+((e*Z2+f*W2)^^{2})^^{2}E = Z2*Z3 F = W2*W3 V = C*D U = V+(ee*E+ff*F)^^{2}W5 = V*Z1+U*W1 Z5 = U*Z1

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