Genus-1 curves over large-characteristic 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.
- 12M for addition with X2=1: 12M. 12M. 12M.
- 10M for addition with Z2=1: 10M.
- 8M for addition with Z1=1 and Z2=1: 8M.
- 12M for readdition: 12M after 12M. 12M after 12M. 12M after 12M. 6M+6S after 6M+12S. 9M+3S after 12M+6S.
- 11M for readdition with X2=1: 5M+6S after 5M+9S.
- 10M for readdition with Z2=1: 10M after 10M.
- 7M for readdition with Z1=1 and Z2=1: 7M after 8M.
- 8M for doubling: 7M+1S. 7M+1S.
- 6M for doubling with Z1=1: 3M+3S.
- 14M for tripling: 8M+6S.
- 102M for scaling: 1I+2M.

- 12M for addition: 12M. 12M. 12M.
- 12M for addition with X2=1: 12M. 12M. 12M.
- 10M for addition with Z2=1: 10M.
- 8M for addition with Z1=1 and Z2=1: 8M.
- 10.8M for readdition: 6M+6S after 6M+12S.
- 10M for readdition with Z2=1: 10M after 10M.
- 9.8M for readdition with X2=1: 5M+6S after 5M+9S.
- 7M for readdition with Z1=1 and Z2=1: 7M after 8M.
- 7.8M for doubling: 3M+6S. 3M+6S. 7M+1S. 7M+1S.
- 5.4M for doubling with Z1=1: 3M+3S.
- 12.8M for tripling: 8M+6S.
- 102M for scaling: 1I+2M.

- 12M for addition: 12M. 12M. 12M.
- 11.03M for addition with X2=1: 5M+9S.
- 10M for addition with Z2=1: 10M.
- 8M for addition with Z1=1 and Z2=1: 8M.
- 10.02M for readdition: 6M+6S after 6M+12S.
- 10M for readdition with Z2=1: 10M after 10M.
- 9.02M for readdition with X2=1: 5M+6S after 5M+9S.
- 7M for readdition with Z1=1 and Z2=1: 7M after 8M.
- 7.02M for doubling: 3M+6S. 3M+6S.
- 5.01M for doubling with Z1=1: 3M+3S.
- 12.02M for tripling: 8M+6S.
- 102M 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 | 12M | |

addition | X2=1 | 5M + 9S | 5M + 6S |

addition | 6M + 12S | 6M + 6S | |

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

doubling | Z1=1 | 3M + 3S | |

doubling | 7M + 1S | ||

doubling | 7M + 1S | ||

doubling | 3M + 6S | ||

doubling | 3M + 6S | ||

doubling | 6M + 3S | ||

doubling | 12M | ||

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

tripling | 3*b*d=1 | 8M + 6S + 1*b | |

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.
- Source: 2009 Bernstein–Kohel–Lange (introduction).
- Strongly unified.
- Explicit formulas:
Y1X2 = Y1*X2 Y1Y2 = Y1*Y2 Z1Y2 = Z1*Y2 Z1Z2 = Z1*Z2 X1Z2 = X1*Z2 X1X2 = X1*X2 X3 = Z1Z2*Z1Y2-X1X2*Y1X2 Y3 = Y1Y2*Y1X2-Z1Z2*X1Z2 Z3 = X1X2*X1Z2-Y1Y2*Z1Y2

- 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

- Assumptions: X2=1.
- Cost: 5M + 9S + 15add + 2*2.
- Cost: 5M + 6S + 12add dependent upon the first point.
- Source: 2007 Hisil–Carter–Dawson.
- Explicit formulas:
S0 = Y2^

^{2}S1 = Z2^^{2}S2 = (Y2+Z2)^^{2}-S0-S1 S3 = 2*Y2 S4 = 2*Z2 R0 = X1^^{2}R1 = Y1^^{2}R2 = Z1^^{2}R3 = X1+Y1 Y3 = Y1+Z1 Y3 = Y3^^{2}Z3 = X1+Z1 Z3 = Z3^^{2}X3 = R3^^{2}R3 = Y3-R1 R3 = R3-R2 Y3 = R0*S2 Y3 = Y3-R3 R3 = X3-R0 R3 = R3-R1 Z3 = Z3-R0 Z3 = Z3-R2 X3 = R1*S4 R0 = Z3*S0 X3 = X3-R0 Z3 = R2*S3 R0 = R3*S1 Z3 = Z3-R0

- Cost: 6M + 12S + 21add.
- Cost: 6M + 6S + 12add dependent upon the first point.
- Source: 2008.02.25 Hisil–Wong–Carter–Dawson, page 10, top.
- Explicit formulas:
XX1 = X1^

^{2}YY1 = Y1^^{2}ZZ1 = Z1^^{2}XY1 = (X1+Y1)^^{2}-XX1-YY1 XZ1 = (X1+Z1)^^{2}-XX1-ZZ1 YZ1 = (Y1+Z1)^^{2}-YY1-ZZ1 XX2 = X2^^{2}YY2 = Y2^^{2}ZZ2 = Z2^^{2}XY2 = (X2+Y2)^^{2}-XX2-YY2 XZ2 = (X2+Z2)^^{2}-XX2-ZZ2 YZ2 = (Y2+Z2)^^{2}-YY2-ZZ2 X3 = YY1*XZ2-XZ1*YY2 Y3 = XX1*YZ2-YZ1*XX2 Z3 = ZZ1*XY2-XY1*ZZ2

- 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

- Assumptions: Z1=1.
- Cost: 3M + 3S + 11add + 3*2.
- Source: 2007 Hisil–Carter–Dawson.
- Explicit formulas:
A = X1^

^{2}B = Y1^^{2}D = A+B G = (X1+Y1)^^{2}-D X3 = (2*Y1-G)*(X1+A+1) Y3 = (G-2*X1)*(Y1+B+1) Z3 = (X1-Y1)*(G+2*D)

- 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: 3M + 6S + 15add + 3*2.
- Source: 2007 Hisil–Carter–Dawson.
- Explicit formulas:
A = X1^

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

- Cost: 3M + 6S + 15add + 3*2.
- Source: 2007 Hisil–Carter–Dawson.
- Explicit formulas:
R0 = X1^

^{2}R1 = Y1^^{2}R2 = Z1^^{2}R3 = R0+R1 R4 = R0+R2 R5 = R1+R2 R0 = X1+Y1 R0 = R0^^{2}R0 = R0-R3 R1 = X1+Z1 R1 = R1^^{2}R1 = R1-R4 R2 = Y1+Z1 R3 = 2*R3 R2 = R2^^{2}R4 = 2*R4 R2 = R2-R5 R5 = 2*R5 X3 = R2-R0 R4 = R1+R4 X3 = X3*R4 Y3 = R0-R1 R5 = R2+R5 Y3 = Y3*R5 Z3 = R1-R2 R0 = R0+R3 Z3 = Z3*R0

- 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: 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: 3*b*d=1.
- Cost: 8M + 6S + 1*b + 12add + 2*2.
- Source: 2007 Hisil–Carter–Dawson.
- Explicit formulas:
R0 = X1^

^{2}X3 = R0*X1 R0 = Y1^^{2}Y3 = R0*Y1 R0 = Z1^^{2}Z3 = R0*Z1 R0 = X3-Y3 R0 = R0^^{2}R1 = X3-Z3 R1 = R1^^{2}R2 = Y3-Z3 R2 = R2^^{2}Z3 = Z3+X3 Z3 = Z3+Y3 Z3 = b*Z3 R3 = R0+R2 R0 = R0+R1 R4 = R1+R3 Z3 = Z3*R4 R4 = R1-R3 R4 = R4*X3 R3 = R2-R0 R3 = Y3*R3 X3 = X3*R2 X3 = 2*X3 X3 = X3-R3 Y3 = Y3*R1 Y3 = 2*Y3 Y3 = Y3-R4

- 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