Genus-1 curves over large-characteristic fields

Short Weierstrass curves

y^^{2}=x^^{3}+a*x+b

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

x=X/Z

- 7M for doubling: 2M+5S. 3M+4S. 4M+3S.
- 9M for differential addition: 7M+2S.
- 8M for differential addition with Z1=1: 6M+2S. 6M+2S. 6M+2S.
- 16M for differential addition and doubling: 9M+7S.
- 15M for differential addition and doubling with Z1=1: 8M+7S. 8M+7S. 8M+7S. 8M+7S. 9M+6S.

- 6M for doubling: 2M+5S.
- 8.6M for differential addition: 7M+2S.
- 7.6M for differential addition with Z1=1: 6M+2S. 6M+2S. 6M+2S.
- 14.6M for differential addition and doubling: 9M+7S.
- 13.6M for differential addition and doubling with Z1=1: 8M+7S. 8M+7S. 8M+7S. 8M+7S.

- 5.35M for doubling: 2M+5S.
- 8.34M for differential addition: 7M+2S.
- 7.34M for differential addition with Z1=1: 6M+2S. 6M+2S. 6M+2S.
- 13.69M for differential addition and doubling: 9M+7S.
- 12.69M for differential addition and doubling with Z1=1: 8M+7S. 8M+7S. 8M+7S. 8M+7S.

- Assumptions: b2=2*b and b4=4*b.
- Cost: 2M + 5S + 1*b2 + 1*a + 1*b4 + 7add + 1*2.
- Source: 2002 Brier–Joye "Weierstrass elliptic curves and side-channel attacks", formula (10) accompanied by note "7 multiplications plus 2 multiplications by a constant", plus common-subexpression elimination emphasizing squaring.
- Explicit formulas:
XX = X1^

^{2}ZZ = Z1^^{2}A = 2*((X1+Z1)^^{2}-XX-ZZ) aZZ = a*ZZ X3 = (XX-aZZ)^^{2}-b2*A*ZZ Z3 = A*(XX+aZZ)+b4*ZZ^^{2}

- Assumptions: b2=2*b.
- Cost: 3M + 4S + 1*b2 + 1*a + 7add + 2*2.
- Source: 2002 Brier–Joye "Weierstrass elliptic curves and side-channel attacks", formula (10) accompanied by note "7 multiplications plus 2 multiplications by a constant", plus common-subexpression elimination.
- Explicit formulas:
XX = X1^

^{2}ZZ = Z1^^{2}A = 2*((X1+Z1)^^{2}-XX-ZZ) aZZ = a*ZZ b2ZZ = b2*ZZ X3 = (XX-aZZ)^^{2}-A*b2ZZ Z3 = A*(XX+aZZ)+2*b2ZZ*ZZ

- Cost: 4M + 3S + 1*a + 1*b + 4add + 1*4 + 1*8.
- Source: 2002 Izu–Takagi "A fast parallel elliptic curve multiplication resistant against side channel attacks", page 296, Formula 3.
- Explicit formulas:
T1 = X1^

^{2}T2 = Z1^^{2}T3 = a*T2 T4 = T1-T3 T5 = T4^^{2}T6 = b*T2 T7 = X1*Z1 T8 = T6*T7 T9 = 8*T8 X3 = T5-T9 T10 = T1+T3 T11 = T7*T10 T12 = T6*T2 T13 = T11+T12 Z3 = 4*T13

- Cost: 3M + 5S + 1^
^{3}+ 1^^{4}+ 2*a + 2*b + 4add + 1*4 + 1*8. - Source: 2002 Izu–Takagi "A fast parallel elliptic curve multiplication resistant against side channel attacks", formula (10).
- Explicit formulas:
X3 = (X1^

^{2}-a*Z1^^{2})^^{2}-8*b*X1*Z1^^{3}Z3 = 4*(X1*Z1*(X1^^{2}+a*Z1^^{2})+b*Z1^^{4})

- Cost: 3M + 4S + 3^
^{3}+ 2*a + 2*b + 4add + 1*4 + 1*8. - Source: 2002 Brier–Joye "Weierstrass elliptic curves and side-channel attacks", formula (10) accompanied by note "7 multiplications plus 2 multiplications by a constant".
- Explicit formulas:
X3 = (X1^

^{2}-a*Z1^^{2})^^{2}-8*b*X1*Z1^^{3}Z3 = 4*Z1*(X1^^{3}+a*X1*Z1^^{2}+b*Z1^^{3})

- Assumptions: Z1=1 and b4=4*b.
- Cost: 6M + 2S + 1*a + 1*b4 + 4add.
- Source: 2002 Brier–Joye "Weierstrass elliptic curves and side-channel attacks", formula (9) accompanied by note "7 multiplications plus 3 multiplications by a constant", plus common-subexpression elimination.
- Explicit formulas:
A = X2*X3 B = Z2*Z3 C = X2*Z3 D = Z2*X3 X5 = (A-a*B)^

^{2}-b4*B*(C+D) Z5 = X1*(C-D)^^{2}

- Assumptions: Z1=1.
- Cost: 6M + 2S + 1*a + 1*b + 4add + 1*4.
- Source: 2002 Izu–Takagi "A fast parallel elliptic curve multiplication resistant against side channel attacks", page 295, Formula 1, plus assumption Z1 = 1.
- Explicit formulas:
T1 = X2*X3 T2 = Z2*Z3 T3 = X2*Z3 T4 = Z2*X3 T5 = a*T2 T6 = T1-T5 T7 = T6^

^{2}T8 = b*T2 T9 = 4*T8 T10 = T3+T4 T11 = T9*T10 T12 = T7-T11 X5 = T12 T13 = T3-T4 T14 = T13^^{2}Z5 = X1*T14

- Assumptions: Z1=1.
- Cost: 6M + 2S + 1*a + 1*b + 5add + 1*2 + 1*4.
- Source: 2002 Izu–Takagi "A fast parallel elliptic curve multiplication resistant against side channel attacks", page 296, Formula 2, plus assumption Z1 = 1.
- Explicit formulas:
T1 = X2*X3 T2 = Z2*Z3 T3 = X2*Z3 T4 = X3*Z2 T5 = T3+T4 T6 = a*T2 T7 = T1+T6 T8 = T5*T7 T9 = 2*T8 T10 = T2^

^{2}T11 = b*T10 T12 = 4*T11 T13 = T9+T12 T14 = T3-T4 T15 = T14^^{2}T16 = T13 T17 = X1*T15 X5 = T16-T17 Z5 = T15

- Cost: 7M + 2S + 1*a + 1*b + 4add + 1*4.
- Source: 2002 Izu–Takagi "A fast parallel elliptic curve multiplication resistant against side channel attacks", page 295, Formula 1.
- Explicit formulas:
T1 = X2*X3 T2 = Z2*Z3 T3 = X2*Z3 T4 = Z2*X3 T5 = a*T2 T6 = T1-T5 T7 = T6^

^{2}T8 = b*T2 T9 = 4*T8 T10 = T3+T4 T11 = T9*T10 T12 = T7-T11 X5 = Z1*T12 T13 = T3-T4 T14 = T13^^{2}Z5 = X1*T14

- Cost: 8M + 2S + 1*a + 1*b + 5add + 1*2 + 1*4.
- Source: 2002 Izu–Takagi "A fast parallel elliptic curve multiplication resistant against side channel attacks", page 296, Formula 2.
- Explicit formulas:
T1 = X2*X3 T2 = Z2*Z3 T3 = X2*Z3 T4 = X3*Z2 T5 = T3+T4 T6 = a*T2 T7 = T1+T6 T8 = T5*T7 T9 = 2*T8 T10 = T2^

^{2}T11 = b*T10 T12 = 4*T11 T13 = T9+T12 T14 = T3-T4 T15 = T14^^{2}T16 = Z1*T13 T17 = X1*T15 X5 = T16-T17 Z5 = Z1*T15

- Assumptions: Z1=1.
- Cost: 9M + 2S + 1*a + 1*b + 4add + 1*4.
- Source: 2002 Brier–Joye "Weierstrass elliptic curves and side-channel attacks", formula (9) accompanied by note "7 multiplications plus 3 multiplications by a constant".
- Explicit formulas:
X5 = (X2*X3-a*Z2*Z3)^

^{2}-4*b*Z2*Z3*(X2*Z3+X3*Z2) Z5 = X1*(X2*Z3-X3*Z2)^^{2}

- Assumptions: Z1=1.
- Cost: 9M + 2S + 1*a + 1*b + 4add + 1*4.
- Source: 2002 Izu–Takagi "A fast parallel elliptic curve multiplication resistant against side channel attacks", formula (8), plus assumption Z1 = 1.
- Explicit formulas:
X5 = (X2*X3-a*Z2*Z3)^

^{2}-4*b*Z2*Z3*(X2*Z3+X3*Z2) Z5 = X1*(X2*Z3-X3*Z2)^^{2}

- Assumptions: Z1=1.
- Cost: 9M + 3S + 1*a + 1*b + 5add + 1*2 + 1*4.
- Source: 2002 Izu–Takagi "A fast parallel elliptic curve multiplication resistant against side channel attacks", formula (9), plus assumption Z1 = 1.
- Explicit formulas:
R = 2*(X2*Z3+X3*Z2)*(X2*X3+a*Z2*Z3)+4*b*Z2^

^{2}*Z3^^{2}S = (X2*Z3-X3*Z2)^^{2}X5 = R-S*X1 Z5 = S

- Cost: 10M + 2S + 1*a + 1*b + 4add + 1*4.
- Source: 2002 Izu–Takagi "A fast parallel elliptic curve multiplication resistant against side channel attacks", formula (8).
- Explicit formulas:
X5 = Z1*((X2*X3-a*Z2*Z3)^

^{2}-4*b*Z2*Z3*(X2*Z3+X3*Z2)) Z5 = X1*(X2*Z3-X3*Z2)^^{2}

- Cost: 11M + 3S + 1*a + 1*b + 5add + 1*2 + 1*4.
- Source: 2002 Izu–Takagi "A fast parallel elliptic curve multiplication resistant against side channel attacks", formula (9).
- Explicit formulas:
R = 2*(X2*Z3+X3*Z2)*(X2*X3+a*Z2*Z3)+4*b*Z2^

^{2}*Z3^^{2}S = (X2*Z3-X3*Z2)^^{2}X5 = R*Z1-S*X1 Z5 = S*Z1

- Assumptions: Z1=1 and b2=2*b and b4=4*b.
- Cost: 8M + 7S + 1*b2 + 2*a + 2*b4 + 11add + 1*2.
- Source: 2002 Brier–Joye "Weierstrass elliptic curves and side-channel attacks", formulas (9) and (10), plus common-subexpression elimination emphasizing squarings.
- Explicit formulas:
XX = X2^

^{2}ZZ = Z2^^{2}E = 2*((X2+Z2)^^{2}-XX-ZZ) aZZ = a*ZZ X4 = (XX-aZZ)^^{2}-b2*E*ZZ Z4 = E*(XX+aZZ)+b4*ZZ^^{2}A = X2*X3 B = Z2*Z3 C = X2*Z3 D = Z2*X3 X5 = (A-a*B)^^{2}-b4*B*(C+D) Z5 = X1*(C-D)^^{2}

- Assumptions: Z1=1 and b4=4*b.
- Cost: 8M + 7S + 2*a + 3*b4 + 11add + 1*2.
- Source: 2002 Izu–Takagi "A fast parallel elliptic curve multiplication resistant against side channel attacks", formulas (8) and (10), plus common-subexpression elimination, plus assumption Z1=1.
- Explicit formulas:
XX = X2^

^{2}ZZ = Z2^^{2}aZZ = a*ZZ E = (X2+Z2)^^{2}-XX-ZZ X4 = (XX-aZZ)^^{2}-b4*E*ZZ Z4 = 2*E*(XX+aZZ)+b4*ZZ^^{2}A = X2*X3 B = Z2*Z3 C = X2*Z3 D = X3*Z2 X5 = (A-a*B)^^{2}-b4*B*(C+D) Z5 = X1*(C-D)^^{2}

- Assumptions: Z1=1 and b4=4*b.
- Cost: 8M + 7S + 2*a + 3*b4 + 12add + 2*2.
- Source: 2002 Izu–Takagi "A fast parallel elliptic curve multiplication resistant against side channel attacks", formulas (9) and (10), plus common-subexpression elimination, plus assumption Z1=1.
- Explicit formulas:
XX = X2^

^{2}ZZ = Z2^^{2}aZZ = a*ZZ E = (X2+Z2)^^{2}-XX-ZZ X4 = (XX-aZZ)^^{2}-b4*E*ZZ Z4 = 2*E*(XX+aZZ)+b4*ZZ^^{2}A = X2*X3 B = Z2*Z3 C = X2*Z3 D = X3*Z2 R = 2*(C+D)*(A+a*B)+b4*B^^{2}S = (C-D)^^{2}X5 = R-S*X1 Z5 = S

- Assumptions: Z1=1 and b4=4*b.
- Cost: 8M + 7S + 2*a + 3*b4 + 12add + 2*2.
- Source: 2002 Izu–Takagi "A fast parallel elliptic curve multiplication resistant against side channel attacks", formulas (9) and (10), plus common-subexpression elimination, plus assumption Z1=1.
- Explicit formulas:
XX = X2^

^{2}ZZ = Z2^^{2}aZZ = a*ZZ E = (X2+Z2)^^{2}-XX-ZZ X4 = (XX-aZZ)^^{2}-b4*E*ZZ Z4 = 2*E*(XX+aZZ)+b4*ZZ^^{2}A = X2*X3 B = Z2*Z3 C = X2*Z3 D = X3*Z2 R = 2*(C+D)*(A+a*B)+b4*B^^{2}S = (C-D)^^{2}X5 = R-S*X1 Z5 = S

- Assumptions: Z1=1 and b2=2*b and b4=4*b.
- Cost: 9M + 6S + 1*b2 + 2*a + 1*b4 + 11add + 2*2.
- Source: 2002 Brier–Joye "Weierstrass elliptic curves and side-channel attacks", formulas (9) and (10), plus common-subexpression elimination.
- Explicit formulas:
XX = X2^

^{2}ZZ = Z2^^{2}E = 2*((X2+Z2)^^{2}-XX-ZZ) aZZ = a*ZZ b2ZZ = b2*ZZ X4 = (XX-aZZ)^^{2}-E*b2ZZ Z4 = E*(XX+aZZ)+2*b2ZZ*ZZ A = X2*X3 B = Z2*Z3 C = X2*Z3 D = Z2*X3 X5 = (A-a*B)^^{2}-b4*B*(C+D) Z5 = X1*(C-D)^^{2}

- Assumptions: b4=4*b.
- Cost: 9M + 7S + 2*a + 3*b4 + 11add + 1*2.
- Source: 2002 Izu–Takagi "A fast parallel elliptic curve multiplication resistant against side channel attacks", formulas (8) and (10), plus common-subexpression elimination.
- Explicit formulas:
XX = X2^

^{2}ZZ = Z2^^{2}aZZ = a*ZZ E = (X2+Z2)^^{2}-XX-ZZ X4 = (XX-aZZ)^^{2}-b4*E*ZZ Z4 = 2*E*(XX+aZZ)+b4*ZZ^^{2}A = X2*X3 B = Z2*Z3 C = X2*Z3 D = X3*Z2 X5 = Z1*((A-a*B)^^{2}-b4*B*(C+D)) Z5 = X1*(C-D)^^{2}

- Assumptions: b4=4*b.
- Cost: 10M + 7S + 2*a + 3*b4 + 12add + 2*2.
- Source: 2002 Izu–Takagi "A fast parallel elliptic curve multiplication resistant against side channel attacks", formulas (9) and (10), plus common-subexpression elimination.
- Explicit formulas:
XX = X2^

^{2}ZZ = Z2^^{2}aZZ = a*ZZ E = (X2+Z2)^^{2}-XX-ZZ X4 = (XX-aZZ)^^{2}-b4*E*ZZ Z4 = 2*E*(XX+aZZ)+b4*ZZ^^{2}A = X2*X3 B = Z2*Z3 C = X2*Z3 D = X3*Z2 R = 2*(C+D)*(A+a*B)+b4*B^^{2}S = (C-D)^^{2}X5 = R*Z1-S*X1 Z5 = S*Z1

- Assumptions: Z1=1.
- Cost: 12M + 7S + 1^
^{3}+ 1^^{4}+ 3*a + 3*b + 8add + 2*4 + 1*8. - Source: 2002 Izu–Takagi "A fast parallel elliptic curve multiplication resistant against side channel attacks", formulas (8) and (10), plus assumption Z1 = 1.
- Explicit formulas:
X4 = (X2^

^{2}-a*Z2^^{2})^^{2}-8*b*X2*Z2^^{3}Z4 = 4*(X2*Z2*(X2^^{2}+a*Z2^^{2})+b*Z2^^{4}) X5 = ((X2*X3-a*Z2*Z3)^^{2}-4*b*Z2*Z3*(X2*Z3+X3*Z2)) Z5 = X1*(X2*Z3-X3*Z2)^^{2}

- Assumptions: Z1=1.
- Cost: 12M + 8S + 1^
^{3}+ 1^^{4}+ 3*a + 3*b + 9add + 1*2 + 2*4 + 1*8. - Source: 2002 Izu–Takagi "A fast parallel elliptic curve multiplication resistant against side channel attacks", formulas (9) and (10), plus assumption Z1 = 1.
- Explicit formulas:
X4 = (X2^

^{2}-a*Z2^^{2})^^{2}-8*b*X2*Z2^^{3}Z4 = 4*(X2*Z2*(X2^^{2}+a*Z2^^{2})+b*Z2^^{4}) R = 2*(X2*Z3+X3*Z2)*(X2*X3+a*Z2*Z3)+4*b*Z2^^{2}*Z3^^{2}S = (X2*Z3-X3*Z2)^^{2}X5 = R-S*X1 Z5 = S

- Cost: 13M + 7S + 1^
^{3}+ 1^^{4}+ 3*a + 3*b + 8add + 2*4 + 1*8. - Source: 2002 Izu–Takagi "A fast parallel elliptic curve multiplication resistant against side channel attacks", formulas (8) and (10).
- Explicit formulas:
X4 = (X2^

^{2}-a*Z2^^{2})^^{2}-8*b*X2*Z2^^{3}Z4 = 4*(X2*Z2*(X2^^{2}+a*Z2^^{2})+b*Z2^^{4}) X5 = Z1*((X2*X3-a*Z2*Z3)^^{2}-4*b*Z2*Z3*(X2*Z3+X3*Z2)) Z5 = X1*(X2*Z3-X3*Z2)^^{2}

- Cost: 14M + 8S + 1^
^{3}+ 1^^{4}+ 3*a + 3*b + 9add + 1*2 + 2*4 + 1*8. - Source: 2002 Izu–Takagi "A fast parallel elliptic curve multiplication resistant against side channel attacks", formulas (9) and (10).
- Explicit formulas:
X4 = (X2^

^{2}-a*Z2^^{2})^^{2}-8*b*X2*Z2^^{3}Z4 = 4*(X2*Z2*(X2^^{2}+a*Z2^^{2})+b*Z2^^{4}) R = 2*(X2*Z3+X3*Z2)*(X2*X3+a*Z2*Z3)+4*b*Z2^^{2}*Z3^^{2}S = (X2*Z3-X3*Z2)^^{2}X5 = R*Z1-S*X1 Z5 = S*Z1

- Assumptions: Z1=1.
- Cost: 12M + 6S + 3^
^{3}+ 3*a + 3*b + 8add + 2*4 + 1*8. - Source: 2002 Brier–Joye "Weierstrass elliptic curves and side-channel attacks", formulas (9) and (10).
- Explicit formulas:
X4 = (X2^

^{2}-a*Z2^^{2})^^{2}-8*b*X2*Z2^^{3}Z4 = 4*Z2*(X2^^{3}+a*X2*Z2^^{2}+b*Z2^^{3}) X5 = (X2*X3-a*Z2*Z3)^^{2}-4*b*Z2*Z3*(X2*Z3+X3*Z2) Z5 = X1*(X2*Z3-X3*Z2)^^{2}