Genus-1 curves over large-characteristic fields

Jacobi quartics

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

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

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

This representation was introduced by Hisil, Carter, and Dawson in the paper "New formulae for efficient elliptic curve arithmetic" at Indocrypt 2007.

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

- 10.2M for addition: 7M+4S.
- 8.4M for addition with Z2=1: 6M+3S.
- 9.4M for readdition: 7M+3S after 7M+4S.
- 8.4M for readdition with Z2=1: 6M+3S after 6M+3S.
- 6M for doubling: 2M+5S.
- 4.8M for doubling with Z1=1: 6S.
- 12.8M for tripling: 4M+11S. 8M+6S.
- 103.6M for scaling: 1I+2M+2S.

- 9.68M for addition: 7M+4S.
- 8.01M for addition with Z2=1: 6M+3S.
- 9.01M for readdition: 7M+3S after 7M+4S.
- 8.01M for readdition with Z2=1: 6M+3S after 6M+3S.
- 5.35M for doubling: 2M+5S.
- 4.02M for doubling with Z1=1: 6S.
- 11.37M for tripling: 4M+11S.
- 103.34M for scaling: 1I+2M+2S.

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

addition | Z2=1 and k=a-1 | 6M + 3S + 1*k | 6M + 3S + 1*k |

addition | k=a-1 | 7M + 4S + 1*k | 7M + 3S + 1*k |

doubling | Z1=1 | 6S + 1*a | |

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

doubling | 2M + 5S + 1*a | ||

doubling | 3M + 4S | ||

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

doubling | a2=2*a | 3M + 8S + 1*a2 + 1*a | |

tripling | 8M + 6S + 1*a | ||

tripling | b=a^^{2}-1 |
4M + 11S + 1*a + 1*b | |

scaling | 1I + 2M + 2S |

- Assumptions: Z2=1 and k=a-1.
- Cost: 6M + 3S + 1*k + 16add + 4*2.
- Cost: 6M + 3S + 1*k + 14add + 3*2 dependent upon the first point.
- Source: 2008.02.25 Hisil–Wong–Carter–Dawson, plus U=XX, plus V=ZZ, plus W=R/2, plus rescaling, plus denominator elimination, plus standard streamlining, plus Z2=1.
- Strongly unified.
- Explicit formulas:
R1 = (X1+Z1)^

^{2}-XX1-ZZ1 R2 = 2*X2 A = 2*XX1*XX2 B = 2*ZZ1 C = R1*R2 D = Y1*Y2 X3 = (R1+Y1)*(R2+Y2)-C-D Z3 = B-A XX3 = X3^^{2}ZZ3 = Z3^^{2}F = A+B+C G = 2*((XX1+ZZ1)*(XX2+1)+D)+k*C H = XX3+ZZ3 Y3 = F*G-H

- Assumptions: k=a-1.
- Cost: 7M + 4S + 1*k + 19add + 3*2.
- Cost: 7M + 3S + 1*k + 14add + 3*2 dependent upon the first point.
- Source: 2008.02.25 Hisil–Wong–Carter–Dawson, plus U=XX, plus V=ZZ, plus W=R/2, plus rescaling, plus denominator elimination, plus standard streamlining.
- Strongly unified.
- Explicit formulas:
R1 = (X1+Z1)^

^{2}-XX1-ZZ1 R2 = (X2+Z2)^^{2}-XX2-ZZ2 A = 2*XX1*XX2 B = 2*ZZ1*ZZ2 C = R1*R2 D = Y1*Y2 X3 = (R1+Y1)*(R2+Y2)-C-D Z3 = B-A XX3 = X3^^{2}ZZ3 = Z3^^{2}F = A+B+C G = 2*((XX1+ZZ1)*(XX2+ZZ2)+D)+k*C H = XX3+ZZ3 Y3 = F*G-H

- Assumptions: Z1=1.
- Cost: 6S + 1*a + 6add + 1*2.
- Source: 2009 Hisil–Wong–Carter–Dawson, formula (9), plus substitutions U = XX, V = ZZ, W = R/2, plus R rotation, plus assumption Z1=1, plus standard simplification.
- Explicit formulas:
YY1 = Y1^

^{2}X3 = (X1+Y1)^^{2}-XX1-YY1 Z3 = 1-XX1^^{2}XX3 = X3^^{2}ZZ3 = Z3^^{2}Y3 = 2*YY1^^{2}-a*XX3-ZZ3

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

^{2}B = Y1^^{2}X3 = XX1+B-(X1+Y1)^^{2}Z3 = A-1 XX3 = X3^^{2}ZZ3 = Z3^^{2}T3 = XX3+ZZ3 Y3 = 2*B*(A+2*XX1+1)-T3

- Cost: 2M + 5S + 1*a + 7add + 1*2.
- Source: 2009 Hisil–Wong–Carter–Dawson, formula (9), plus substitutions U = XX, V = ZZ, W = R/2, plus R rotation.
- Explicit formulas:
R1 = (X1+Z1)^

^{2}-XX1-ZZ1 YY1 = Y1^^{2}X3 = Y1*R1 Z3 = (ZZ1-XX1)*(ZZ1+XX1) XX3 = X3^^{2}ZZ3 = Z3^^{2}Y3 = 2*YY1^^{2}-a*XX3-ZZ3

- Cost: 3M + 4S + 6add + 1*2.
- Source: 2007 Hisil–Carter–Dawson.
- Explicit formulas:
B = XX1-ZZ1 T1 = XX1+ZZ1 C = Y1*T1 X3 = C-Y1*(X1+Z1)^

^{2}Z3 = T1*B XX3 = X3^^{2}ZZ3 = Z3^^{2}T3 = XX3+ZZ3 Y3 = 2*C^^{2}-T3

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

^{2}-XX1-ZZ1 A1 = (R1+2*Y1)^^{2}A2 = 4*Y1^^{2}Q1 = XX1^^{2}S1 = R1^^{2}S12 = 2*S1 M = a*S12 A2M = A2-M X3 = A1-A2-S1 Y3 = A2M*(A2+M)+S12^^{2}Z3 = A2M-8*Q1 XX3 = X3^^{2}ZZ3 = Z3^^{2}

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

^{2}A2 = Y1^^{2}Q1 = (X1^^{2})^^{2}S1 = (X1*Z1)^^{2}T = A2-Q1-2*a*S1 X3 = A1-A2-S1 Y3 = (T+Q1)*(A2+a2*S1)+4*S1^^{2}Z3 = T-Q1 XX3 = X3^^{2}ZZ3 = Z3^^{2}T3 = XX3+ZZ3

- Cost: 8M + 6S + 1*a + 12add + 4*2.
- Source: 2007 Hisil–Carter–Dawson.
- Explicit formulas:
A = XX1^

^{2}B = ZZ1^^{2}C = A+B D = 2*((XX1+ZZ1)^^{2}-C) E = A-B F = 2*A G = 2*B J = a*D+2*C K = J+E L = J-E M = C*E N = G*K P = F*L X3 = X1*(M-N) Y3 = Y1*((M+N)*(P-M)+(D*E)^^{2}) Z3 = Z1*(P+M) XX3 = X3^^{2}ZZ3 = Z3^^{2}

- Assumptions: b=a^
^{2}-1. - Cost: 4M + 11S + 1*a + 1*b + 13add + 2*2 + 2*4.
- Source: 2007 Hisil–Carter–Dawson.
- Explicit formulas:
UU = XX1^

^{2}WW = ZZ1^^{2}RR = ((X1+Z1)^^{2}-XX1-ZZ1)^^{2}A = 4*(UU-WW) AA = A^^{2}B = 2*(UU+WW)+a*RR BB = B^^{2}AB = (A+B)^^{2}-AA-BB C = b*RR^^{2}Q = 2*(BB-C) X3 = X1*(AB-Q) Z3 = Z1*(AB+Q) Y3 = Y1*(Q^^{2}-4*AA*C) XX3 = X3^^{2}ZZ3 = Z3^^{2}

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

^{2}Y3 = Y1*A^^{2}Z3 = 1 ZZ3 = 1