Genus-1 curves over large-characteristic fields

Jacobi quartics

y^^{2}=x^^{4}+2*a*x^^{2}+1

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

x=X/Z y=Y/Z^^{2}

- 13M for addition: 10M+3S.
- 11M for addition with Z2=1: 8M+3S.
- 7M for addition with Z1=1 and Z2=1: 5M+2S.
- 11M for readdition: 8M+3S after 8M+6S. 9M+2S after 10M+4S. 9M+2S after 10M+4S.
- 11M for readdition with Z2=1: 8M+3S after 8M+3S. 8M+3S after 8M+6S. 9M+2S after 10M+4S. 9M+2S after 10M+4S.
- 7M for readdition with Z1=1 and Z2=1: 5M+2S after 5M+2S.
- 8M for doubling: 2M+6S. 2M+6S.
- 5M for doubling with Z1=1: 1M+4S.
- 103M for scaling: 1I+2M+1S.

- 12.4M for addition: 10M+3S.
- 10.4M for addition with Z2=1: 8M+3S.
- 6.6M for addition with Z1=1 and Z2=1: 5M+2S.
- 10.4M for readdition: 8M+3S after 8M+6S.
- 10.4M for readdition with Z2=1: 8M+3S after 8M+3S. 8M+3S after 8M+6S.
- 6.6M for readdition with Z1=1 and Z2=1: 5M+2S after 5M+2S.
- 6.8M for doubling: 2M+6S. 2M+6S.
- 4.2M for doubling with Z1=1: 1M+4S.
- 102.8M for scaling: 1I+2M+1S.

- 12.01M for addition: 10M+3S.
- 10.01M for addition with Z2=1: 8M+3S.
- 6.34M for addition with Z1=1 and Z2=1: 5M+2S.
- 10.01M for readdition: 8M+3S after 8M+6S.
- 10.01M for readdition with Z2=1: 8M+3S after 8M+3S. 8M+3S after 8M+6S.
- 6.34M for readdition with Z1=1 and Z2=1: 5M+2S after 5M+2S.
- 6.02M for doubling: 2M+6S. 2M+6S.
- 3.68M for doubling with Z1=1: 1M+4S.
- 102.67M for scaling: 1I+2M+1S.

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

addition | Z1=1 and Z2=1 | 5M + 2S + 1*a | 5M + 2S + 1*a |

addition | Z2=1 | 8M + 3S + 1*a | 8M + 3S + 1*a |

addition | 10M + 3S + 1*a | 9M + 3S + 1*a | |

addition | 8M + 6S + 1*a | 8M + 3S + 1*a | |

addition | 10M + 4S + 1*a | 9M + 2S + 1*a | |

addition | b=-2*a | 10M + 4S + 1*b | 9M + 2S + 1*b |

addition | 19M + 8S + 1*a | 18M + 6S + 1*a | |

addition | Z1=1 and Z2=1 | 2I + 11M + 5S + 1*a | 2I + 11M + 4S + 1*a |

doubling | a2=2*a and Z1=1 | 1M + 4S + 1*a2 | |

doubling | b=4-4*a^^{2} |
2M + 6S + 1*a + 1*b | |

doubling | a2=2*a | 2M + 6S + 1*a2 | |

doubling | a2=2*a | 3M + 6S + 2*a2 | |

doubling | 1M + 9S + 1*a | ||

doubling | 19M + 8S + 1*a | ||

doubling | 19M + 8S + 1*a | ||

scaling | 1I + 2M + 1S |

- Assumptions: Z1=1 and Z2=1.
- Cost: 5M + 2S + 1*a + 10add + 1*2.
- Cost: 5M + 2S + 1*a + 9add + 1*2 dependent upon the first point.
- Source: 2002 Billet–Joye "The Jacobi model of an elliptic curve and side-channel analysis", page 6, plus specialization to Z1=1 and Z2=1.
- Strongly unified.
- Explicit formulas:
T7 = Y1+X1 T8 = Y2+X2 T2 = Y1*Y2 T7 = T7*T8 T7 = T7-T2 T5 = X1*X2 T6 = T5 X3 = T7-T6 T1 = X1+X2 T3 = T1^

^{2}T6 = 2*T6 T3 = T3-T6 T3 = T3*T6 T4 = a*T6 T2 = T2+T4 T8 = T5^^{2}T5 = T8+1 T2 = T2*T5 Y3 = T2+T3 Z3 = 1-T8

- Assumptions: Z2=1.
- Cost: 8M + 3S + 1*a + 13add + 1*2.
- Cost: 8M + 3S + 1*a + 11add + 1*2 dependent upon the first point.
- Source: 2002 Billet–Joye "The Jacobi model of an elliptic curve and side-channel analysis", page 6, plus specialization to Z2=1.
- Strongly unified.
- Explicit formulas:
T1 = X1 T2 = Y1 T3 = Z1 T4 = X2 T5 = Y2 T7 = T1*T3 T7 = T2+T7 T8 = T4 T8 = T5+T8 T2 = T2*T5 T7 = T7*T8 T7 = T7-T2 T5 = T1*T4 T1 = T1+T3 T8 = T3 T4 = T4+1 T6 = T5*T8 T7 = T7-T6 T1 = T1*T4 T1 = T1-T5 T1 = T1-T8 T3 = T1^

^{2}T6 = 2*T6 T3 = T3-T6 T3 = T3*T6 T4 = a*T6 T2 = T2+T4 T4 = T8^^{2}T8 = T5^^{2}T5 = T4+T8 T2 = T2*T5 T2 = T2+T3 T5 = T4-T8 X3 = T7 Y3 = T2 Z3 = T5

- Cost: 10M + 3S + 1*a + 13add + 1*2.
- Cost: 9M + 3S + 1*a + 11add + 1*2 dependent upon the first point.
- Source: 2002 Billet–Joye "The Jacobi model of an elliptic curve and side-channel analysis", page 6.
- Strongly unified.
- Explicit formulas:
T1 = X1 T2 = Y1 T3 = Z1 T4 = X2 T5 = Y2 T6 = Z2 T7 = T1*T3 T7 = T2+T7 T8 = T4*T6 T8 = T5+T8 T2 = T2*T5 T7 = T7*T8 T7 = T7-T2 T5 = T1*T4 T1 = T1+T3 T8 = T3*T6 T4 = T4+T6 T6 = T5*T8 T7 = T7-T6 T1 = T1*T4 T1 = T1-T5 T1 = T1-T8 T3 = T1^

^{2}T6 = 2*T6 T3 = T3-T6 T3 = T3*T6 T4 = a*T6 T2 = T2+T4 T4 = T8^^{2}T8 = T5^^{2}T5 = T4+T8 T2 = T2*T5 T2 = T2+T3 T5 = T4-T8 X3 = T7 Y3 = T2 Z3 = T5

- Cost: 8M + 6S + 1*a + 15add + 2*2 + 1*4.
- Cost: 8M + 3S + 1*a + 11add + 2*2 + 1*4 dependent upon the first point.
- Source: 2007 Bernstein–Lange.
- Strongly unified.
- Explicit formulas:
A2 = X2^

^{2}C2 = Z2^^{2}D2 = A2+C2 B2 = (X2+Z2)^^{2}-D2 E2 = B2+Y2 A1 = X1^^{2}C1 = Z1^^{2}D1 = A1+C1 B1 = (X1+Z1)^^{2}-D1 E1 = B1+Y1 A1A2 = A1*A2 B1B2 = B1*B2 C1C2 = C1*C2 Y1Y2 = Y1*Y2 F = C1C2+A1A2 G = 2*B1B2 X3 = E1*E2-B1B2-Y1Y2 Y3 = F*(4*Y1Y2+a*G)+(D1*D2-F)*G Z3 = 2*(C1C2-A1A2)

- Cost: 10M + 4S + 1*a + 11add + 1*2.
- Cost: 9M + 2S + 1*a + 9add + 1*2 dependent upon the first point.
- Source: 2002 Billet–Joye "The Jacobi model of an elliptic curve and side-channel analysis", formula (11), plus separation of X2^
^{2},Z2^^{2}as suggested by 2007 Duquesne. - Strongly unified.
- Explicit formulas:
A2 = X2^

^{2}B2 = X2*Z2 C2 = Z2^^{2}A1 = X1^^{2}B1 = X1*Z1 C1 = Z1^^{2}A1A2 = A1*A2 B1B2 = B1*B2 C1C2 = C1*C2 Y1Y2 = Y1*Y2 E = C1C2+A1A2 F = (A1+C1)*(A2+C2)-E G = 2*B1B2 X3 = (B1+Y1)*(B2+Y2)-B1B2-Y1Y2 Y3 = E*(Y1Y2+a*G)+G*F Z3 = C1C2-A1A2

- Assumptions: b=-2*a.
- Cost: 10M + 4S + 1*b + 12add + 1*2.
- Cost: 9M + 2S + 1*b + 10add + 1*2 dependent upon the first point.
- Source: 2007 Duquesne, page 103, Table 1.
- Strongly unified.
- Explicit formulas:
T1 = X1^

^{2}T2 = X2^^{2}T3 = X1*Z1 T4 = X2*Z2 T5 = Z1^^{2}T6 = Z2^^{2}T7 = Y1 T8 = Y2 T9 = T7*T8 T7 = T7+T3 T8 = T8+T4 T3 = T3*T4 T7 = T7*T8 T7 = T7-T9 T7 = T7-T3 T4 = T1*T2 T8 = T5*T6 T1 = T1+T5 T2 = T2+T6 T5 = T1*T2 T5 = T5-T4 T5 = T5-T8 T1 = T8-T4 T2 = T8+T4 T6 = b*T3 T6 = T9-T6 T6 = T6*T2 T3 = 2*T3 T3 = T5*T3 T8 = T6+T3 X3 = T7 Y3 = T8 Z3 = T1

- Cost: 19M + 8S + 1*a + 6add + 2*2.
- Cost: 18M + 6S + 1*a + 6add + 2*2 dependent upon the first point.
- Source: 2002 Billet–Joye "The Jacobi model of an elliptic curve and side-channel analysis", formula (11).
- Strongly unified.
- Explicit formulas:
X3 = X1*Z1*Y2+Y1*X2*Z2 Y3 = ((Z1*Z2)^

^{2}+(X1*X2)^^{2})*(Y1*Y2+2*a*X1*X2*Z1*Z2)+2*X1*X2*Z1*Z2*(X1^^{2}*Z2^^{2}+Z1^^{2}*X2^^{2}) Z3 = (Z1*Z2)^^{2}-(X1*X2)^^{2}

- Assumptions: Z1=1 and Z2=1.
- Cost: 2I + 11M + 5S + 1*a + 6add + 2*2.
- Cost: 2I + 11M + 4S + 1*a + 6add + 2*2 dependent upon the first point.
- Source: 2002 Billet–Joye "The Jacobi model of an elliptic curve and side-channel analysis", formula (11), plus specialization to affine.
- Strongly unified.
- Explicit formulas:
r = 1-(X1*X2)^

^{2}X3 = (X1*Y2+Y1*X2)/r Y3 = ((1+(X1*X2)^^{2})*(Y1*Y2+2*a*X1*X2)+2*X1*X2*(X1^^{2}+X2^^{2}))/r^^{2}Z3 = 1

- Assumptions: a2=2*a and Z1=1.
- Cost: 1M + 4S + 1*a2 + 9add + 1*4.
- Source: 2007 Feng–Wu, first JQN2 doubling formula, plus correction of obvious typos, plus epsilon=1, plus delta=-a, plus Z1=1, plus common-subexpression elimination.
- Explicit formulas:
U1 = (X1+Y1)^

^{2}U2 = Y1^^{2}S1 = X1^^{2}V1 = S1^^{2}aS1 = a2*S1 T = U2-V1-aS1 X3 = U1-U2-S1 Y3 = (T+V1)*(U2+aS1)+4*V1 Z3 = T-V1

- Assumptions: b=4-4*a^
^{2}. - Cost: 2M + 6S + 1*a + 1*b + 5add + 1*2.
- Source: 2007 Hisil–Carter–Dawson.
- Explicit formulas:
T0 = X1*Z1 X3 = T0*Y1 X3 = X3+X3 T0 = T0^

^{2}T1 = 2*a*T0 T2 = Y1^^{2}Z3 = T2-T1 Y3 = T0^^{2}Y3 = b*Y3 T0 = T2^^{2}Y3 = Y3+T0 T0 = X1^^{2}T0 = T0^^{2}Z3 = Z3-T0 Z3 = Z3-T0

- Assumptions: a2=2*a.
- Cost: 2M + 6S + 1*a2 + 9add + 1*2.
- Source: 2007 Feng–Wu, first JQN2 doubling formula, plus correction of obvious typos, plus epsilon=1, plus delta=-a, plus common-subexpression elimination.
- Explicit formulas:
XZ1 = X1*Z1 U1 = (XZ1+Y1)^

^{2}U2 = Y1^^{2}V1 = (X1^^{2})^^{2}S1 = XZ1^^{2}aS1 = a2*S1 T = U2-V1-aS1 X3 = U1-U2-S1 Y3 = (T+V1)*(U2+aS1)+(2*S1)^^{2}Z3 = T-V1

- Assumptions: a2=2*a.
- Cost: 3M + 6S + 2*a2 + 9add + 1*4.
- Source: 2007 Feng–Wu, first JQN2 doubling formula, plus correction of obvious typos, plus epsilon=1, plus substitution delta=-a.
- Explicit formulas:
U1 = (X1*Z1+Y1)^

^{2}U2 = Y1^^{2}V1 = (X1^^{2})^^{2}S1 = (X1*Z1)^^{2}T = U2-V1-a2*S1 X3 = U1-U2-S1 Y3 = (T+V1)*(U2+a2*S1)+4*S1^^{2}Z3 = T-V1

- Cost: 1M + 9S + 1*a + 10add + 2*2 + 1*4.
- Source: 2007 Bernstein–Lange.
- Explicit formulas:
XX = X1^

^{2}XXXX = XX^^{2}YY = Y1^^{2}ZZ = Z1^^{2}ZZZZ = ZZ^^{2}M = XX+ZZ XZ = (X1+Z1)^^{2}-M XZXZ = XZ^^{2}X3 = (Y1+XZ)^^{2}-YY-XZXZ Y3 = (ZZZZ+XXXX)*(4*YY+2*a*XZXZ)+XZXZ^^{2}Z3 = 2*(ZZZZ-XXXX)

- Cost: 19M + 8S + 1*a + 6add + 2*2.
- Source: 2002 Billet–Joye "The Jacobi model of an elliptic curve and side-channel analysis", formula (11), plus specialization to doubling.
- Explicit formulas:
X3 = X1*Z1*Y1+Y1*X1*Z1 Y3 = ((Z1*Z1)^

^{2}+(X1*X1)^^{2})*(Y1*Y1+2*a*X1*X1*Z1*Z1)+2*X1*X1*Z1*Z1*(X1^^{2}*Z1^^{2}+Z1^^{2}*X1^^{2}) Z3 = (Z1*Z1)^^{2}-(X1*X1)^^{2}

- Cost: 19M + 8S + 1*a + 6add + 2*2.
- Source: 2002 Billet–Joye "The Jacobi model of an elliptic curve and side-channel analysis", formula (11).
- Explicit formulas:
X2 = X1 Y2 = Y1 Z2 = Z1 X3 = X1*Z1*Y2+Y1*X2*Z2 Y3 = ((Z1*Z2)^

^{2}+(X1*X2)^^{2})*(Y1*Y2+2*a*X1*X2*Z1*Z2)+2*X1*X2*Z1*Z2*(X1^^{2}*Z2^^{2}+Z1^^{2}*X2^^{2}) Z3 = (Z1*Z2)^^{2}-(X1*X2)^^{2}

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

^{2}Z3 = 1