Ordinary genus-1 curves over binary fields

Hessian curves

x^^{3}+y^^{3}+1=3*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. 12M+6S.
- 10M for addition with Z2=1: 10M.
- 8M for addition with Z1=1 and Z2=1: 8M.
- 9M for readdition: 9M+3S after 12M+6S.
- 9M for readdition with Z2=1: 9M+3S after 12M+6S.
- 7M for readdition with Z1=1 and Z2=1: 7M after 8M.
- 6M for doubling: 6M+3S.
- 11M for tripling: 11M+4S.
- 12M for scaling: 1I+2M.

- 12M for addition: 12M. 12M.
- 10M for addition with Z2=1: 10M.
- 8M for addition with Z1=1 and Z2=1: 8M.
- 9.6M for readdition: 9M+3S after 12M+6S.
- 9.6M for readdition with Z2=1: 9M+3S after 12M+6S.
- 7M for readdition with Z1=1 and Z2=1: 7M after 8M.
- 6.6M for doubling: 6M+3S.
- 11.8M for tripling: 11M+4S.
- 12M for scaling: 1I+2M.

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

addition | Z1=1 and Z2=1 | 8M | 7M |

addition | Z2=1 | 10M | 10M |

addition | 12M | 12M | |

addition | 12M | 12M | |

addition | 12M + 6S | 9M + 3S | |

doubling | 6M + 3S | ||

doubling | 7M + 1S | ||

doubling | 7M + 1S | ||

doubling | 12M | ||

doubling | 3M + 6^^{3} |
||

tripling | a=3*d | 11M + 4S + 2*a | |

tripling | 10M + 1S + 29^^{3} + 2*d |
||

scaling | 1I + 2M |

- Assumptions: Z1=1 and Z2=1.
- Cost: 8M + 3add.
- Cost: 7M + 3add dependent upon the first point.
- Explicit formulas:
X1Y2 = X1*Y2 Y1X2 = Y1*X2 X3 = Y1X2*Y1-Y2*X1Y2 Y3 = X1*X1Y2-Y1X2*X2 Z3 = Y2*X2-X1*Y1

- Assumptions: Z2=1.
- Cost: 10M + 3add.
- Explicit formulas:
X1Y2 = X1*Y2 Y1X2 = Y1*X2 Z1X2 = Z1*X2 Z1Y2 = Z1*Y2 X3 = Y1X2*Y1-Z1Y2*X1Y2 Y3 = X1*X1Y2-Y1X2*Z1X2 Z3 = Z1Y2*Z1X2-X1*Y1

- Cost: 12M + 3add.
- Source: 2001 Joye–Quisquater "Hessian elliptic curves and side-channel attacks".
- Explicit formulas:
T1 = X1 T2 = Y1 T3 = Z1 T4 = X2 T5 = Y2 T6 = Z2 T7 = T1*T6 T1 = T1*T5 T5 = T3*T5 T3 = T3*T4 T4 = T2*T4 T2 = T2*T6 T6 = T2*T7 T2 = T2*T4 T4 = T3*T4 T3 = T3*T5 T5 = T1*T5 T1 = T1*T7 T1 = T1-T4 T2 = T2-T5 T3 = T3-T6 X3 = T2 Y3 = T1 Z3 = T3

- Cost: 12M + 3add.
- Explicit formulas:
X1Y2 = X1*Y2 X1Z2 = X1*Z2 Y1Z2 = Y1*Z2 Y1X2 = Y1*X2 Z1X2 = Z1*X2 Z1Y2 = Z1*Y2 X3 = Y1X2*Y1Z2-Z1Y2*X1Y2 Y3 = X1Z2*X1Y2-Y1X2*Z1X2 Z3 = Z1Y2*Z1X2-X1Z2*Y1Z2

- Cost: 12M + 6S + 3add.
- Cost: 9M + 3S + 3add dependent upon the first point.
- Explicit formulas:
X3 = Y1^

^{2}*Z2*X2-Y2^^{2}*Z1*X1 Y3 = X1^^{2}*Y2*Z2-X2^^{2}*Y1*Z1 Z3 = Z1^^{2}*X2*Y2-Z2^^{2}*X1*Y1

- Cost: 6M + 3S + 3add.
- Explicit formulas:
XX = X1^

^{2}XXX = X1*XX YY = Y1^^{2}YYY = Y1*YY ZZ = Z1^^{2}ZZZ = Z1*ZZ X3 = Y1*(ZZZ-XXX) Y3 = X1*(YYY-ZZZ) Z3 = Z1*(XXX-YYY)

- Cost: 7M + 1S + 8add.
- Source: 2007 Hisil–Carter–Dawson.
- Explicit formulas:
R0 = X1^

^{2}R1 = X1+Y1 R1 = Y1*R1 R2 = Z1+X1 R2 = Z1*R2 R2 = R0+R2 R1 = R0+R1 R0 = X1-Y1 R0 = R1*R0 Z3 = R0*Z1 R1 = Z1-X1 R1 = R2*R1 X3 = R1*Y1 R2 = -(R0+R1) Y3 = R2*X1

- Cost: 7M + 1S + 8add.
- Source: 2007 Hisil–Carter–Dawson.
- Explicit formulas:
A = X1^

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

- Cost: 12M + 3add.
- Source: 2001 Joye–Quisquater "Hessian elliptic curves and side-channel attacks", applying the addition formulas to permuted input coordinates.
- Explicit formulas:
T1 = Z1 T2 = X1 T3 = Y1 T4 = Y1 T5 = Z1 T6 = X1 T7 = T1*T6 T1 = T1*T5 T5 = T3*T5 T3 = T3*T4 T4 = T2*T4 T2 = T2*T6 T6 = T2*T7 T2 = T2*T4 T4 = T3*T4 T3 = T3*T5 T5 = T1*T5 T1 = T1*T7 T1 = T1-T4 T2 = T2-T5 T3 = T3-T6 X3 = T2 Y3 = T1 Z3 = T3

- Cost: 3M + 6^
^{3}+ 3add. - Explicit formulas:
X3 = Y1*(Z1^

^{3}-X1^^{3}) Y3 = X1*(Y1^^{3}-Z1^^{3}) Z3 = Z1*(X1^^{3}-Y1^^{3})

- Assumptions: a=3*d.
- Cost: 11M + 4S + 2*a + 8add.
- Source: 2007 Hisil–Carter–Dawson, plus elimination of common subexpressions.
- Explicit formulas:
XX = X1^

^{2}A = XX*X1 YY = Y1^^{2}B = YY*Y1 ZZ = Z1^^{2}C = ZZ*Z1 AB = A-B BC = B-C CA = C-A U = B*CA V = A*BC X3 = a*(U*AB-V*BC) Y3 = a*(V*AB-U*CA) Z3 = (A+B+C)*(BC*CA-AB^^{2})

- Cost: 10M + 1S + 29^
^{3}+ 2*d + 16add + 2*3. - Source: 2007 Hisil–Carter–Dawson.
- Explicit formulas:
X3 = 3*d*(Y1^

^{3}*(Z1^^{3}-X1^^{3})*(X1^^{3}-Y1^^{3})-X1^^{3}*(Y1^^{3}-Z1^^{3})*(Y1^^{3}-Z1^^{3})) Y3 = 3*d*(X1^^{3}*(Y1^^{3}-Z1^^{3})*(X1^^{3}-Y1^^{3})-Y1^^{3}*(Z1^^{3}-X1^^{3})*(Z1^^{3}-X1^^{3})) Z3 = (X1^^{3}+Y1^^{3}+Z1^^{3})*((Y1^^{3}-Z1^^{3})*(Z1^^{3}-X1^^{3})-(X1^^{3}-Y1^^{3})^^{2})

- Cost: 1I + 2M + 0add.
- Explicit formulas:
A = 1/Z1 X3 = A*X1 Y3 = A*Y1 Z3 = 1