Genus-1 curves over large-characteristic fields

Jacobi intersections

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

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

s=S/Z c=C/Z d=D/Z SC=S*C DZ=D*Z

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

- 11.8M for addition: 11M+1S.
- 11.8M for addition with S2=1: 11M+1S.
- 10.8M for addition with Z2=1: 10M+1S.
- 10.8M for addition with Z1=1 and Z2=1: 10M+1S.
- 11.8M for readdition: 11M+1S after 11M+1S.
- 11.8M for readdition with S2=1: 11M+1S after 11M+1S.
- 10.8M for readdition with Z2=1: 10M+1S after 10M+1S.
- 10.8M for readdition with Z1=1 and Z2=1: 10M+1S after 10M+1S. 10M+1S after 10M+2S.
- 6M for doubling: 2M+5S.
- 6M for doubling with Z1=1: 2M+5S.
- 14M for tripling: 6M+10S. 6M+10S.
- 104M for scaling: 1I+4M.

- 11.67M for addition: 11M+1S.
- 11.67M for addition with S2=1: 11M+1S.
- 10.67M for addition with Z2=1: 10M+1S.
- 10.67M for addition with Z1=1 and Z2=1: 10M+1S.
- 11.67M for readdition: 11M+1S after 11M+1S.
- 11.67M for readdition with S2=1: 11M+1S after 11M+1S.
- 10.67M for readdition with Z2=1: 10M+1S after 10M+1S.
- 10.67M for readdition with Z1=1 and Z2=1: 10M+1S after 10M+1S. 10M+1S after 10M+2S.
- 5.35M for doubling: 2M+5S.
- 5.35M for doubling with Z1=1: 2M+5S.
- 12.7M for tripling: 6M+10S. 6M+10S.
- 104M for scaling: 1I+4M.

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

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

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

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

addition | Z2=1 | 13M + 2S + 1*a | 12M + 2S + 1*a |

addition | S2=1 | 13M + 2S + 1*a | 12M + 2S + 1*a |

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

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

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

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

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

doubling | 5M + 4S | ||

doubling | 6M + 3S | ||

doubling | 7M + 3S | ||

doubling | 14M + 9S | ||

tripling | b=a-1 and b2=2*b and b3=3*b and bb2=2*b*b | 6M + 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 | 6M + 10S + 1*bb2 + 1*b2 + 2*a + 1*b3 | |

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

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

scaling | 1I + 4M |

- Assumptions: Z2=1.
- Cost: 10M + 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:
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 SC3 = S3*C3 DZ3 = D3*Z3

- Assumptions: Z1=1 and Z2=1.
- Cost: 10M + 2S + 1*a + 7add.
- Cost: 10M + 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}SC3 = S3*C3 DZ3 = D3*Z3

- Cost: 11M + 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:
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 SC3 = S3*C3 DZ3 = D3*Z3

- Assumptions: Z2=1.
- Cost: 13M + 2S + 1*a + 7add.
- Cost: 12M + 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}SC3 = S3*C3 DZ3 = D3*Z3

- Assumptions: S2=1.
- Cost: 13M + 2S + 1*a + 7add.
- Cost: 12M + 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}SC3 = S3*C3 DZ3 = D3*Z3

- Cost: 15M + 2S + 1*a + 7add.
- Cost: 13M + 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}SC3 = S3*C3 DZ3 = D3*Z3

- Cost: 16M + 2S + 1*a + 4add.
- Cost: 14M + 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}SC3 = S3*C3 DZ3 = D3*Z3

- Cost: 22M + 2S + 1*a + 4add.
- Cost: 20M + 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}SC3 = S3*C3 DZ3 = D3*Z3

- Cost: 2M + 5S + 1*a + 7add + 1*2.
- Source: 2008.02.25 Hisil–Wong–Carter–Dawson.
- Explicit formulas:
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 SC3 = S3*C3 DZ3 = D3*Z3

- Assumptions: Z1=1.
- Cost: 4M + 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 SC3 = S3*C3 DZ3 = D3*Z3

- Cost: 5M + 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 SC3 = S3*C3 DZ3 = D3*Z3

- Cost: 6M + 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 SC3 = S3*C3 DZ3 = D3*Z3

- Cost: 7M + 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 SC3 = S3*C3 DZ3 = D3*Z3

- Cost: 14M + 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}SC3 = S3*C3 DZ3 = D3*Z3

- Assumptions: b=a-1 and b2=2*b and b3=3*b and bb2=2*b*b.
- Cost: 6M + 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) SC3 = S3*C3 DZ3 = D3*Z3

- Assumptions: b=a-1 and b2=2*b and bb2=2*b*b and b3=3*b.
- Cost: 6M + 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)) SC3 = S3*C3 DZ3 = D3*Z3

- Assumptions: b=a-1.
- Cost: 9M + 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 SC3 = S3*C3 DZ3 = D3*Z3

- Assumptions: b=a-1.
- Cost: 9M + 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) SC3 = S3*C3 DZ3 = D3*Z3

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