Genus-1 curves over large-characteristic fields

Twisted Hessian curves

a*x^^{3}+y^^{3}+1=d*x*y

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

x=X/Z y=Y/Z

- 12M for addition: 12M.
- 12M for readdition: 12M after 12M.
- 8M for doubling: 7M+1S. 8M.
- 14M for tripling: 8M+6S.

- 12M for addition: 12M.
- 12M for readdition: 12M after 12M.
- 7.8M for doubling: 7M+1S.
- 12.8M for tripling: 8M+6S.

- 12M for addition: 12M.
- 12M for readdition: 12M after 12M.
- 7.67M for doubling: 7M+1S.
- 12.02M for tripling: 8M+6S.

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

addition | 12M + 1*a | 12M + 1*a | |

doubling | minustwo=-2 | 7M + 1S + 1*minustwo + 1*d | |

doubling | i^^{2}=-1 and minustwo=-2 and 2d=2*d |
8M + 1*i + 1*minustwo + 1*2d | |

doubling | 6M + 3S + 1*a | ||

doubling | 3M + 3^^{3} + 1*a |
||

tripling | d*recipd=1 | 8M + 6S + 1*a + 1*recipd |

- Cost: 12M + 1*a + 3add.
- Source: 2009 Bernstein–Kohel–Lange.
- Strongly unified.
- Explicit formulas:
A = X1*Z2 B = Z1*Z2 C = Y1*X2 D = Y1*Y2 E = Z1*Y2 F = a*X1*X2 X3 = A*B-C*D Y3 = D*E-F*A Z3 = F*C-B*E

- Assumptions: minustwo=-2.
- Cost: 7M + 1S + 1*minustwo + 1*d + 7add + 1*2 + 1*3.
- Source: 2012 Chuengsatiansup.
- Explicit formulas:
P = Y1*Z1 2P = 2*P S = Y1+Z1 A = S^

^{2}-P C = (A-2P)*S D = A*(Z1-Y1) E = 3*C-d*X1*2P X3 = minustwo*X1*D Y3 = (D-E)*Z1 Z3 = (D+E)*Y1

- Assumptions: i^
^{2}=-1 and minustwo=-2 and 2d=2*d. - Cost: 8M + 1*i + 1*minustwo + 1*2d + 9add + 1*3.
- Source: 2009 Bernstein–Kohel–Lange.
- Explicit formulas:
iZ = i*Z1 A = (Y1-iZ)*(Y1+iZ) B = Y1*Z1 C = (A-B)*(Y1+Z1) D = (A+B)*(Z1-Y1) E = 3*C-2d*X1*B X3 = minustwo*X1*D Y3 = (D-E)*Z1 Z3 = (D+E)*Y1

- Cost: 6M + 3S + 1*a + 3add.
- Source: 2009 Bernstein–Kohel–Lange.
- Explicit formulas:
A = X1^

^{2}B = Y1^^{2}C = Z1^^{2}D = A*X1 E = B*Y1 F = C*Z1 G = a*D X3 = X1*(E-F) Y3 = Z1*(G-E) Z3 = Y1*(F-G)

- Cost: 3M + 3^
^{3}+ 1*a + 3add. - Source: 2009 Bernstein–Kohel–Lange.
- Explicit formulas:
D = X1^

^{3}E = Y1^^{3}F = Z1^^{3}G = a*D X3 = X1*(E-F) Y3 = Z1*(G-E) Z3 = Y1*(F-G)

- Assumptions: d*recipd=1.
- Cost: 8M + 6S + 1*a + 1*recipd + 12add + 2*2.
- Source: 2009 Bernstein–Kohel–Lange.
- Explicit formulas:
U = a*X1*X1^

^{2}V = Y1*Y1^^{2}W = Z1*Z1^^{2}A = (U-V)^^{2}B = (U-W)^^{2}C = (V-W)^^{2}D = A+C E = A+B X3 = recipd*(U+V+W)*(B+D) Y3 = 2*U*C-V*(C-E) Z3 = 2*V*B-U*(B-D)