Genus-1 curves over large-characteristic fields

Jacobi quartics

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

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

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

Source of this representation: 2007 Duquesne, plus extra factor of 2 suggested by 2007 Bernstein–Lange.

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

- 9.4M for addition: 7M+3S.
- 8.4M for addition with Z2=1: 6M+3S.
- 8.2M for addition with Z1=1 and Z2=1: 5M+4S.
- 9.4M for readdition: 7M+3S after 7M+3S.
- 8.4M for readdition with Z2=1: 6M+3S after 6M+3S.
- 8.2M for readdition with Z1=1 and Z2=1: 5M+4S after 5M+4S.
- 6M for doubling: 2M+5S.
- 5.8M for doubling with Z1=1: 1M+6S. 1M+6S.
- 12.8M for tripling: 4M+11S.
- 102.8M for scaling: 1I+2M+1S.

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

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

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

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

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

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

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

addition | b=-2*a and half*2=1 | 9M + 2S + 2*half + 1*b | 9M + 2S + 1*half + 1*b |

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

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

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

doubling | 3M + 4S | ||

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

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

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

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

scaling | 1I + 2M + 1S |

- Assumptions: Z1=1 and Z2=1.
- Cost: 5M + 4S + 1*a + 12add + 1*2.
- Cost: 5M + 4S + 1*a + 11add + 1*2 dependent upon the first point.
- Source: 2007 Bernstein–Lange.
- Strongly unified.
- Explicit formulas:
E1 = X1+Y1 E2 = X2+Y2 B = X1*X2 XX1XX2 = B^

^{2}Y1Y2 = Y1*Y2 F = 1+XX1XX2 G = 2*B X3 = E1*E2-B-Y1Y2 Y3 = F*(Y1Y2+a*G)+(XX1+XX2)*G Z3 = 1-XX1XX2 XX3 = X3^^{2}ZZ3 = Z3^^{2}R3 = (X3+Z3)^^{2}-XX3-ZZ3

- Assumptions: Z2=1 and k=a-1.
- Cost: 6M + 3S + 1*k + 15add + 3*2.
- Cost: 6M + 3S + 1*k + 13add + 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:
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 R3 = (X3+Z3)^^{2}-H

- Assumptions: Z2=1.
- Cost: 7M + 3S + 1*a + 14add + 2*2 + 1*4.
- Cost: 7M + 3S + 1*a + 12add + 2*2 + 1*4 dependent upon the first point.
- Source: 2007 Bernstein–Lange.
- Strongly unified.
- Explicit formulas:
E1 = R1+Y1 E2 = R2+Y2 XX1XX2 = XX1*XX2 R1R2 = R1*R2 Y1Y2 = Y1*Y2 F = ZZ1+XX1XX2 G = 2*R1R2 X3 = E1*E2-R1R2-Y1Y2 Y3 = F*(4*Y1Y2+a*G)+((XX1+ZZ1)*(XX2+ZZ2)-F)*G Z3 = 2*(ZZ1-XX1XX2) XX3 = X3^

^{2}ZZ3 = Z3^^{2}R3 = (X3+Z3)^^{2}-XX3-ZZ3

- Assumptions: k=a-1.
- Cost: 7M + 3S + 1*k + 15add + 3*2.
- Cost: 7M + 3S + 1*k + 13add + 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:
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 R3 = (X3+Z3)^^{2}-H

- Cost: 8M + 3S + 1*a + 14add + 2*2 + 1*4.
- Cost: 8M + 3S + 1*a + 12add + 2*2 + 1*4 dependent upon the first point.
- Source: 2007 Bernstein–Lange.
- Strongly unified.
- Explicit formulas:
E1 = R1+Y1 E2 = R2+Y2 XX1XX2 = XX1*XX2 R1R2 = R1*R2 ZZ1ZZ2 = ZZ1*ZZ2 Y1Y2 = Y1*Y2 F = ZZ1ZZ2+XX1XX2 G = 2*R1R2 X3 = E1*E2-R1R2-Y1Y2 Y3 = F*(4*Y1Y2+a*G)+((XX1+ZZ1)*(XX2+ZZ2)-F)*G Z3 = 2*(ZZ1ZZ2-XX1XX2) XX3 = X3^

^{2}ZZ3 = Z3^^{2}R3 = (X3+Z3)^^{2}-XX3-ZZ3

- Assumptions: b=-2*a and half*2=1.
- Cost: 9M + 2S + 2*half + 1*b + 12add + 2*2.
- Cost: 9M + 2S + 1*half + 1*b + 10add + 2*2 dependent upon the first point.
- Source: 2007 Duquesne, page 103, Table 1, plus V=R/2.
- Strongly unified.
- Explicit formulas:
A1 = XX1 A2 = XX2 A3 = half*R1 A4 = half*R2 A5 = ZZ1 A6 = ZZ2 A7 = Y1 A8 = Y2 A9 = A7*A8 A7 = A7+A3 A8 = A8+A4 A3 = A3*A4 A7 = A7*A8 A7 = A7-A9 A7 = A7-A3 A4 = A1*A2 A8 = A5*A6 A1 = A1+A5 A2 = A2+A6 A5 = A1*A2 A5 = A5-A4 A5 = A5-A8 A1 = A8-A4 A2 = A8+A4 A6 = b*A3 A6 = A9-A6 A6 = A6*A2 A3 = 2*A3 A3 = A5*A3 A8 = A6+A3 A2 = A7^

^{2}A4 = A1*A7 A6 = A1^^{2}X3 = A7 Y3 = A8 Z3 = A1 XX3 = A2 R3 = 2*A4 ZZ3 = A6

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

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

- Assumptions: Z1=1.
- Cost: 1M + 6S + 10add + 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 R3 = (X3+Z3)^^{2}-T3 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.
- Explicit formulas:
YY1 = Y1^

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

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

^{2}ZZ3 = Z3^^{2}T3 = XX3+ZZ3 R3 = (X3+Z3)^^{2}-T3 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:
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}T3 = XX3+ZZ3 R3 = (X3+Z3)^^{2}-T3

- Assumptions: a2=2*a.
- Cost: 3M + 9S + 2*a2 + 12add + 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-a2*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 R3 = (X3+Z3)^^{2}-T3

- 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 = R1^^{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}R3 = (X3+Z3)^^{2}-XX3-ZZ3

- Cost: 8M + 7S + 1*a + 15add + 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}R3 = (X3+Z3)^^{2}-XX3-ZZ3

- Cost: 1I + 2M + 1S + 0add + 3*2.
- Explicit formulas:
A = 2*ZZ1 B = 1/A X3 = R1*B Y3 = 2*Y1*B XX3 = X3^

^{2}R3 = 2*X3 Z3 = 1 ZZ3 = 1