Genus-1 curves over large-characteristic fields

Short Weierstrass curves

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

Modified Jacobian coordinates [database entry] represent x y as X Y Z T satisfying the following equations:

x=X/Z^^{2}y=Y/Z^^{3}T=a*Z^^{4}

- 18M for addition: 11M+7S. 12M+6S.
- 13M for addition with Z2=1: 7M+6S.
- 7M for addition with Z1=1 and Z2=1: 3M+4S.
- 16M for readdition: 10M+6S after 11M+7S. 11M+5S after 12M+6S.
- 13M for readdition with Z2=1: 7M+6S after 7M+6S.
- 7M for readdition with Z1=1 and Z2=1: 3M+4S after 3M+4S.
- 8M for doubling: 3M+5S. 4M+4S.
- 7M for doubling with Z1=1: 2M+5S.

- 16.6M for addition: 11M+7S.
- 11.8M for addition with Z2=1: 7M+6S.
- 6.2M for addition with Z1=1 and Z2=1: 3M+4S.
- 14.8M for readdition: 10M+6S after 11M+7S.
- 11.8M for readdition with Z2=1: 7M+6S after 7M+6S.
- 6.2M for readdition with Z1=1 and Z2=1: 3M+4S after 3M+4S.
- 7M for doubling: 3M+5S.
- 6M for doubling with Z1=1: 2M+5S.

- 15.69M for addition: 11M+7S.
- 11.02M for addition with Z2=1: 7M+6S.
- 5.68M for addition with Z1=1 and Z2=1: 3M+4S.
- 14.02M for readdition: 10M+6S after 11M+7S.
- 11.02M for readdition with Z2=1: 7M+6S after 7M+6S.
- 5.68M for readdition with Z1=1 and Z2=1: 3M+4S after 3M+4S.
- 6.35M for doubling: 3M+5S.
- 5.35M for doubling with Z1=1: 2M+5S.

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

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

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

addition | 11M + 7S + 1*a | 10M + 6S + 1*a | |

addition | 12M + 6S + 1*a | 11M + 5S + 1*a | |

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

doubling | 3M + 5S | ||

doubling | 4M + 4S |

- Assumptions: Z1=1 and Z2=1.
- Cost: 3M + 4S + 1*a + 9add + 5*2 + 1*4 + 1*16.
- Source: 2009.04.27 Bernstein–Lange.
- Explicit formulas:
H = X2-X1 HH = H^

^{2}HHHH = HH^^{2}Z3 = 2*H ZZ3 = 4*HH J = 2*((H+HH)^^{2}-HH-HHHH) r = 2*(Y2-Y1) V = X1*ZZ3 X3 = r^^{2}-J-2*V Y3 = r*(V-X3)-2*Y1*J T3 = 16*a*HHHH

- Assumptions: Z2=1.
- Cost: 7M + 6S + 1*a + 9add + 3*2 + 1*4.
- Source: 2009.04.27 Bernstein–Lange.
- Explicit formulas:
ZZ1 = Z1^

^{2}H = X2*ZZ1-X1 HH = H^^{2}I = 4*HH J = H*I r = 2*(Y2*Z1*ZZ1-Y1) V = X1*I X3 = r^^{2}-J-2*V Y3 = r*(V-X3)-2*Y1*J Z3 = (Z1+H)^^{2}-ZZ1-HH ZZ3 = Z3^^{2}T3 = a*ZZ3^^{2}

- Cost: 11M + 7S + 1*a + 9add + 4*2.
- Cost: 10M + 6S + 1*a + 9add + 4*2 dependent upon the first point.
- Source: 2009.04.01 Bernstein–Lange.
- Explicit formulas:
ZZ1 = Z1^

^{2}ZZ2 = Z2^^{2}U1 = X1*ZZ2 U2 = X2*ZZ1 S1 = Y1*Z2*ZZ2 S2 = Y2*Z1*ZZ1 H = U2-U1 I = (2*H)^^{2}J = H*I r = 2*(S2-S1) V = U1*I X3 = r^^{2}-J-2*V Y3 = r*(V-X3)-2*S1*J Z3 = ((Z1+Z2)^^{2}-ZZ1-ZZ2)*H ZZ3 = Z3^^{2}T3 = a*ZZ3^^{2}

- Cost: 12M + 6S + 1*a + 6add + 1*2.
- Cost: 11M + 5S + 1*a + 6add + 1*2 dependent upon the first point.
- Source: 1998 Cohen–Miyaji–Ono "Efficient elliptic curve exponentiation using mixed coordinates", formula (9), plus common-subexpression elimination.
- Explicit formulas:
ZZ1 = Z1^

^{2}ZZ2 = Z2^^{2}U1 = X1*ZZ2 U2 = X2*ZZ1 S1 = Y1*Z2*ZZ2 S2 = Y2*Z1*ZZ1 H = U2-U1 HH = H^^{2}HHH = H*HH r = S2-S1 V = U1*HH X3 = r^^{2}-HHH-2*V Y3 = r*(V-X3)-S1*HHH Z3 = Z1*Z2*H ZZ3 = Z3^^{2}T3 = a*ZZ3^^{2}

- Assumptions: Z1=1.
- Cost: 2M + 5S + 7add + 5*2 + 1*3.
- Source: 2009.04.27 Bernstein–Lange.
- Explicit formulas:
XX = X1^

^{2}A = 2*Y1^^{2}AA = A^^{2}U = 2*AA S = (X1+A)^^{2}-XX-AA M = 3*XX+T1 X3 = M^^{2}-2*S Y3 = M*(S-X3)-U Z3 = 2*Y1 T3 = 2*U*T1

- Cost: 3M + 5S + 7add + 5*2 + 1*3.
- Source: 2009.04.01 Bernstein–Lange.
- Explicit formulas:
XX = X1^

^{2}A = 2*Y1^^{2}AA = A^^{2}U = 2*AA S = (X1+A)^^{2}-XX-AA M = 3*XX+T1 X3 = M^^{2}-2*S Y3 = M*(S-X3)-U Z3 = 2*Y1*Z1 T3 = 2*U*T1

- Cost: 4M + 4S + 4add + 3*2 + 1*3 + 1*4 + 1*8.
- Source: 1998 Cohen–Miyaji–Ono "Efficient elliptic curve exponentiation using mixed coordinates", formula (10), plus common-subexpression elimination.
- Explicit formulas:
XX = X1^

^{2}YY = Y1^^{2}U = 8*YY^^{2}S = 4*X1*YY M = 3*XX+T1 X3 = M^^{2}-2*S Y3 = M*(S-X3)-U Z3 = 2*Y1*Z1 T3 = 2*U*T1