Ordinary genus-1 curves over binary fields

Binary Edwards curves

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

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

d1=d2and represent x y as X Y satisfying the following equations:

x=X y=Y

- 28M for addition: 2I+8M+2S.
- 27M for readdition: 2I+7M+2S after 2I+8M+2S.
- 11M for doubling: 1I+1M+4S.
- 0M for scaling: 0M.

- 28.4M for addition: 2I+8M+2S.
- 27.4M for readdition: 2I+7M+2S after 2I+8M+2S.
- 11.8M for doubling: 1I+1M+4S.
- 0M for scaling: 0M.

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

addition | 2I + 8M + 2S + 2*d1 + 1*d2 | 2I + 7M + 2S + 2*d1 + 1*d2 | |

doubling | 1I + 1M + 4S + 2*d1 | ||

doubling | d2d1=d2/d1 | 1I + 2M + 4S + 1*d2 + 1*d2d1 | |

doubling | 4I + 4M + 10S + 6^^{4} + 4*d2 |
||

scaling | 0M |

- Cost: 2I + 8M + 2S + 2*d1 + 1*d2 + 16add.
- Cost: 2I + 7M + 2S + 2*d1 + 1*d2 + 13add dependent upon the first point.
- Source: 2008 Bernstein–Lange–Rezaeian Farashahi.
- Strongly unified.
- Explicit formulas:
w1 = X1+Y1 w2 = X2+Y2 A = X1^

^{2}+X1 B = Y1^^{2}+Y1 C = d2*w1*w2 D = X2*Y2 X3 = Y1+(C+d1*(w1+X2)+A*(D+X2))/(d1+A*w2) Y3 = X1+(C+d1*(w1+Y2)+B*(D+Y2))/(d1+B*w2)

- Cost: 1I + 1M + 4S + 2*d1 + 8add.
- Source: 2008 Bernstein–Lange–Rezaeian Farashahi.
- Explicit formulas:
A = X1^

^{2}B = A^^{2}C = Y1^^{2}D = C^^{2}E = A+C F = 1/(d1+E+B+D) X3 = (d1*E+A+B)*F Y3 = X3+1+d1*F

- Assumptions: d2d1=d2/d1.
- Cost: 1I + 2M + 4S + 1*d2 + 1*d2d1 + 10add.
- Source: 2008 Bernstein–Lange–Rezaeian Farashahi.
- Explicit formulas:
A = X1^

^{2}B = A^^{2}C = Y1^^{2}D = C^^{2}E = A+C F = B+D G = 1/(d1+E+d2d1*F) X3 = 1+(d1+d2*E+C+D)*G Y3 = X3+(E+F)*G

- Cost: 4I + 4M + 10S + 6^
^{4}+ 4*d2 + 18add. - Source: 2008 Bernstein–Lange–Rezaeian Farashahi.
- Explicit formulas:
X3 = 1+(d1+d2*(X1^

^{2}+Y1^^{2})+Y1^^{2}+Y1^^{4})/(d1+X1^^{2}+Y1^^{2}+(d2/d1)*(X1^^{4}+Y1^^{4})) Y3 = 1+(d1+d2*(X1^^{2}+Y1^^{2})+X1^^{2}+X1^^{4})/(d1+X1^^{2}+Y1^^{2}+(d2/d1)*(X1^^{4}+Y1^^{4}))

- Cost: 0add.
- Explicit formulas:
X3 = X1 Y3 = Y1