Genus-1 curves over large-characteristic fields

Jacobi intersections

s^^{2}+c^^{2}=1 a*s^^{2}+d^^{2}=1

Projective coordinates [database entry] represent s c d as S C D Z satisfying the following equations:

s=S/Z c=C/Z d=D/Z

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

- 13.8M for addition: 13M+1S.
- 12.6M for addition with S2=1: 11M+2S.
- 11.8M for addition with Z2=1: 11M+1S.
- 9.6M for addition with Z1=1 and Z2=1: 8M+2S.
- 11.8M for readdition: 11M+1S after 13M+1S.
- 11.6M for readdition with S2=1: 10M+2S after 11M+2S.
- 10.8M for readdition with Z2=1: 10M+1S after 11M+1S.
- 8.8M for readdition with Z1=1 and Z2=1: 8M+1S after 8M+2S.
- 6M for doubling: 2M+5S.
- 4.8M for doubling with Z1=1: 6S.
- 12M for tripling: 4M+10S. 4M+10S.
- 103M for scaling: 1I+3M.

- 13.67M for addition: 13M+1S.
- 12.34M for addition with S2=1: 11M+2S.
- 11.67M for addition with Z2=1: 11M+1S.
- 9.34M for addition with Z1=1 and Z2=1: 8M+2S.
- 11.67M for readdition: 11M+1S after 13M+1S.
- 11.34M for readdition with S2=1: 10M+2S after 11M+2S.
- 10.67M for readdition with Z2=1: 10M+1S after 11M+1S.
- 8.67M for readdition with Z1=1 and Z2=1: 8M+1S after 8M+2S.
- 5.35M for doubling: 2M+5S.
- 4.02M for doubling with Z1=1: 6S.
- 10.7M for tripling: 4M+10S. 4M+10S.
- 103M for scaling: 1I+3M.

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

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

addition | Z2=1 | 11M + 1S + 2*a | 10M + 1S + 2*a |

addition | Z2=1 | 11M + 2S + 1*a | 10M + 2S + 1*a |

addition | S2=1 | 11M + 2S + 1*a | 10M + 2S + 1*a |

addition | 13M + 1S + 2*a | 11M + 1S + 2*a | |

addition | 13M + 2S + 1*a | 11M + 2S + 1*a | |

addition | 14M + 2S + 1*a | 12M + 2S + 1*a | |

addition | 20M + 2S + 1*a | 18M + 2S + 1*a | |

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

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

doubling | Z1=1 | 2M + 4S | |

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

doubling | 3M + 4S | ||

doubling | 4M + 3S | ||

doubling | 5M + 3S | ||

doubling | 12M + 9S | ||

tripling | b=a-1 and b2=2*b and b3=3*b and bb2=2*b*b | 4M + 10S + 1*bb2 + 1*b2 + 2*a + 1*b3 | |

tripling | b=a-1 and b2=2*b and bb2=2*b*b and b3=3*b | 4M + 10S + 1*bb2 + 1*b2 + 2*a + 1*b3 | |

tripling | b=a-1 | 7M + 7S + 3*b | |

tripling | b=a-1 | 7M + 7S + 5*b | |

scaling | 1I + 3M |

- Assumptions: Z1=1 and Z2=1.
- Cost: 8M + 2S + 1*a + 7add.
- Cost: 8M + 1S + 1*a + 7add dependent upon the first point.
- Source: 2001 Liardet–Smart "Preventing SPA/DPA in ECC systems using the Jacobi form", plus Z1=1, plus Z2=1.
- Strongly unified.
- Explicit formulas:
S1D2 = S1*D2 D1S2 = D1*S2 U = C2*C1 V = D1S2*S1D2 S3 = (C2+D1S2)*(C1+S1D2)-U-V C3 = U-V D3 = D1*D2-a*S1*S2*U Z3 = C2^

^{2}+D1S2^^{2}

- Assumptions: Z2=1.
- Cost: 11M + 1S + 2*a + 14add + 1*2.
- Cost: 10M + 1S + 2*a + 13add + 1*2 dependent upon the first point.
- Source: 2008.02.25 Hisil–Wong–Carter–Dawson, page 6.
- Strongly unified.
- Explicit formulas:
SC1 = S1*C1 DZ1 = D1*Z1 SC2 = S2*C2 E = S1*D2 G = D1*S2 H = Z1*C2 J = SC1*D2 K = DZ1*SC2 S3 = (H+C1)*(E+G)-J-K C3 = (H+E)*(C1-G)-J+K D3 = (DZ1-a*SC1)*(SC2+D2)+a*J-K Z3 = (H+G)^

^{2}-2*K

- Assumptions: Z2=1.
- Cost: 11M + 2S + 1*a + 7add.
- Cost: 10M + 2S + 1*a + 7add dependent upon the first point.
- Source: 2001 Liardet–Smart "Preventing SPA/DPA in ECC systems using the Jacobi form", plus substitution Z2=1.
- Strongly unified.
- Explicit formulas:
Z1C2 = Z1*C2 S1D2 = S1*D2 D1S2 = D1*S2 U = Z1C2*C1 V = D1S2*S1D2 S3 = (Z1C2+D1S2)*(C1+S1D2)-U-V C3 = U-V D3 = Z1*D1*D2-a*S1*C1*S2*C2 Z3 = Z1C2^

^{2}+D1S2^^{2}

- Assumptions: S2=1.
- Cost: 11M + 2S + 1*a + 7add.
- Cost: 10M + 2S + 1*a + 7add dependent upon the first point.
- Source: 2001 Liardet–Smart "Preventing SPA/DPA in ECC systems using the Jacobi form", plus substitution S2=1 (as suggested by 2007 Hisil–Carter–Dawson).
- Strongly unified.
- Explicit formulas:
Z2D2 = Z2*D2 E = Z1*C2 F = S1*D2 G = C1*Z2 H = E*G J = D1*F S3 = (E+D1)*(G+F)-H-J C3 = H-J D3 = Z1*D1*Z2D2-a*S1*C1*C2 Z3 = E^

^{2}+D1^^{2}

- Cost: 13M + 1S + 2*a + 14add + 1*2.
- Cost: 11M + 1S + 2*a + 13add + 1*2 dependent upon the first point.
- Source: 2008.02.25 Hisil–Wong–Carter–Dawson, page 6.
- Strongly unified.
- Explicit formulas:
SC1 = S1*C1 DZ1 = D1*Z1 SC2 = S2*C2 DZ2 = D2*Z2 E = S1*D2 F = C1*Z2 G = D1*S2 H = Z1*C2 J = SC1*DZ2 K = DZ1*SC2 S3 = (H+F)*(E+G)-J-K C3 = (H+E)*(F-G)-J+K D3 = (DZ1-a*SC1)*(SC2+DZ2)+a*J-K Z3 = (H+G)^

^{2}-2*K

- Cost: 13M + 2S + 1*a + 7add.
- Cost: 11M + 2S + 1*a + 7add dependent upon the first point.
- Source: 2001 Liardet–Smart "Preventing SPA/DPA in ECC systems using the Jacobi form".
- Strongly unified.
- Explicit formulas:
Z1C2 = Z1*C2 S1D2 = S1*D2 D1S2 = D1*S2 C1Z2 = C1*Z2 U = Z1C2*C1Z2 V = D1S2*S1D2 S3 = (Z1C2+D1S2)*(C1Z2+S1D2)-U-V C3 = U-V D3 = Z1*D1*Z2*D2-a*S1*C1*S2*C2 Z3 = Z1C2^

^{2}+D1S2^^{2}

- Cost: 14M + 2S + 1*a + 4add.
- Cost: 12M + 2S + 1*a + 4add dependent upon the first point.
- Source: 1986 Chudnovsky–Chudnovsky "Sequences of numbers generated by addition in formal groups and new primality and factorization tests", formula (4.9i), plus common-subexpression elimination.
- Strongly unified.
- Explicit formulas:
Z1C2 = Z1*C2 S1D2 = S1*D2 D1S2 = D1*S2 C1Z2 = C1*Z2 S3 = Z1C2*S1D2+D1S2*C1Z2 C3 = Z1C2*C1Z2-D1S2*S1D2 D3 = Z1*D1*Z2*D2-a*S1*C1*S2*C2 Z3 = Z1C2^

^{2}+D1S2^^{2}

- Cost: 20M + 2S + 1*a + 4add.
- Cost: 18M + 2S + 1*a + 4add dependent upon the first point.
- Source: 1986 Chudnovsky–Chudnovsky "Sequences of numbers generated by addition in formal groups and new primality and factorization tests", formula (4.9i).
- Strongly unified.
- Explicit formulas:
S3 = Z1*C2*S1*D2+D1*S2*C1*Z2 C3 = Z1*C2*C1*Z2-D1*S2*S1*D2 D3 = Z1*D1*Z2*D2-a*S1*C1*S2*C2 Z3 = (Z1*C2)^

^{2}+(D1*S2)^^{2}

- Assumptions: Z1=1.
- Cost: 6S + 1*a + 11add + 2*2 + 3*4.
- Source: 2009.04.27 Bernstein.
- Explicit formulas:
SS1 = S1^

^{2}CC1 = 1-SS1 SC1 = (S1+C1)^^{2}-SS1-CC1 E = D1^^{2}F = SC1^^{2}G = a*F Z3 = 4*E+G D3 = 4*E-G C3 = 2*(F+4*CC1^^{2})-Z3 S3 = 2*((SC1+D1)^^{2}-E-F)

- Assumptions: Z1=1.
- Cost: 1M + 5S + 1*a + 7add + 1*2.
- Source: 2008.02.25 Hisil–Wong–Carter–Dawson, plus assumption Z1=1.
- Explicit formulas:
SC1 = S1*C1 E = D1^

^{2}F = SC1^^{2}G = a*F Z3 = E+G D3 = E-G CC1 = C1^^{2}C3 = 2*(F+CC1^^{2})-Z3 S3 = (SC1+D1)^^{2}-E-F

- Assumptions: Z1=1.
- Cost: 2M + 4S + 5add + 1*2.
- Source: 2007 Bernstein–Lange.
- Explicit formulas:
a0 = S1 a1 = C1 a2 = D1 m = a1^

^{2}l2 = a0*a2 n = l2^^{2}l3 = 2*(a1*a2)^^{2}r3 = m+n r0 = (a1+l2)^^{2}-r3 r1 = m-n r2 = l3-r1 S3 = r0 C3 = r1 D3 = r2 Z3 = r3

- Cost: 2M + 5S + 1*a + 7add + 1*2.
- Source: 2008.02.25 Hisil–Wong–Carter–Dawson.
- Explicit formulas:
SC1 = S1*C1 DZ1 = D1*Z1 E = DZ1^

^{2}F = SC1^^{2}G = a*F Z3 = E+G D3 = E-G CC1 = C1^^{2}C3 = 2*(F+CC1^^{2})-Z3 S3 = (SC1+DZ1)^^{2}-E-F

- Cost: 3M + 4S + 5add + 1*2.
- Source: 2007 Bernstein–Lange.
- Explicit formulas:
a0 = S1 a1 = C1 a2 = D1 a3 = Z1 l1 = a3*a1 m = l1^

^{2}l2 = a0*a2 n = l2^^{2}l3 = 2*(a1*a2)^^{2}r3 = m+n r0 = (l1+l2)^^{2}-r3 r1 = m-n r2 = l3-r1 S3 = r0 C3 = r1 D3 = r2 Z3 = r3

- Cost: 4M + 3S + 5add + 3*2.
- Source: 2001 Liardet–Smart "Preventing SPA/DPA in ECC systems using the Jacobi form".
- Explicit formulas:
a0 = S1 a1 = C1 a2 = D1 a3 = Z1 l1 = a3*a1 l2 = a0*a2 l3 = 2*(a1*a2)^

^{2}r0 = 2*l1*l2 r3 = (l1+l2)^^{2}-r0 r1 = r3-2*l2^^{2}r2 = -r1+l3 S3 = r0 C3 = r1 D3 = r2 Z3 = r3

- Cost: 5M + 3S + 5add + 1*2.
- Source: 1986 Chudnovsky–Chudnovsky "Sequences of numbers generated by addition in formal groups and new primality and factorization tests", formula 4.9ii, plus common-subexpression elimination.
- Explicit formulas:
C1Z1 = C1*Z1 C1D1 = C1*D1 D1Z1 = D1*Z1 D1S1 = D1*S1 U = C1Z1^

^{2}V = C1D1^^{2}W = D1Z1^^{2}UV = U-V S3 = 2*C1Z1*D1S1 C3 = U-W+V D3 = W-UV Z3 = W+UV

- Cost: 12M + 9S + 6add + 1*2.
- Source: 1986 Chudnovsky–Chudnovsky "Sequences of numbers generated by addition in formal groups and new primality and factorization tests", formula 4.9ii.
- Explicit formulas:
S3 = 2*C1*Z1*D1*S1 C3 = (C1*Z1)^

^{2}-(D1*Z1)^^{2}+(C1*D1)^^{2}D3 = (D1*Z1)^^{2}-(C1*Z1)^^{2}+(C1*D1)^^{2}Z3 = (D1*Z1)^^{2}+(C1*Z1)^^{2}-(C1*D1)^^{2}

- Assumptions: b=a-1 and b2=2*b and b3=3*b and bb2=2*b*b.
- Cost: 4M + 10S + 1*bb2 + 1*b2 + 2*a + 1*b3 + 21add + 4*2.
- Source: 2007 Hisil–Carter–Dawson, plus common-subexpression elimination.
- Explicit formulas:
E = S1^

^{2}F = C1^^{2}G = E^^{2}H = F^^{2}J = G^^{2}K = H^^{2}L = (E+F)^^{2}-H-G M = L^^{2}N = (G+L)^^{2}-J-M P = (H+L)^^{2}-K-M R = bb2*J Q = b2*N T = b3*M U = 2*P V = 2*K W = a*U Y = a*Q RV = R-V RQ = R-Q UV = U+V TW = T+W TY = T-Y RQUV = RQ+UV S3 = S1*(RV+TW-2*UV) C3 = C1*(RV-TY+2*RQ) D3 = D1*(TW-RQUV) Z3 = Z1*(TY-RQUV)

- Assumptions: b=a-1 and b2=2*b and bb2=2*b*b and b3=3*b.
- Cost: 4M + 10S + 1*bb2 + 1*b2 + 2*a + 1*b3 + 29add + 4*2.
- Source: 2007 Hisil–Carter–Dawson.
- Explicit formulas:
E = S1^

^{2}F = C1^^{2}G = E^^{2}H = F^^{2}J = G^^{2}K = H^^{2}L = (E+F)^^{2}-H-G M = L^^{2}N = (G+L)^^{2}-J-M P = (H+L)^^{2}-K-M R = bb2*J Q = b2*N T = b3*M U = 2*P V = 2*K W = a*U Y = a*Q S3 = S1*((R-V)+(T+W)-2*(U+V)) C3 = C1*((R-V)-(T-Y)+2*(R-Q)) D3 = D1*((T+W)-(R-Q)-(U+V)) Z3 = Z1*((T-Y)-(R-Q)-(U+V))

- Assumptions: b=a-1.
- Cost: 7M + 7S + 3*b + 16add + 4*2.
- Source: 2007 Hisil–Carter–Dawson.
- Explicit formulas:
R0 = S1^

^{2}R1 = C1^^{2}R2 = R0^^{2}R3 = R1^^{2}R4 = 2*R3 R5 = 2*R4 R6 = 2*R1 R6 = R6+R0 R6 = R6^^{2}R6 = R6-R2 R6 = R6-R5 R2 = b*R2 R5 = R5+R4 R4 = R2^^{2}R0 = R5*R2 R5 = R2*R6 R2 = R3^^{2}R1 = R3*R6 R3 = R4-R2 R2 = R4+R2 R4 = 2*R3 R3 = b*R1 R6 = b*R5 R3 = R0+R3 R1 = R1+R2 R0 = R0-R6 R2 = R5-R2 R5 = R3+R4 R5 = R5-R1 S3 = S1*R5 R4 = R4-R2 R4 = R4-R0 C3 = C1*R4 R2 = R2+R3 D3 = D1*R2 R0 = R0-R1 Z3 = Z1*R0

- Assumptions: b=a-1.
- Cost: 7M + 7S + 5*b + 24add + 5*2.
- Source: 2007 Hisil–Carter–Dawson.
- Explicit formulas:
E = S1^

^{2}F = C1^^{2}G = E^^{2}H = F^^{2}J = 2*H K = 2*J L = (2*F+E)^^{2}-G-K M = b*G N = K+J P = M^^{2}R = N*M U = M*L V = H^^{2}W = H*L S3 = S1*(R+b*W+2*(P-V)-W-P-V) C3 = C1*(2*(P-V)-U+P+V-R+b*U) D3 = D1*(U-P-V+R+b*W) Z3 = Z1*(R-b*U-W-P-V)

- Cost: 1I + 3M + 0add.
- Explicit formulas:
A = 1/Z1 S3 = S1*A C3 = C1*A D3 = D1*A Z3 = 1