Genus-1 curves over large-characteristic fields

Short Weierstrass curves

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

XYZZ coordinates with a4=-3 [database entry] make the additional assumptions

a=-3and represent x y as X Y ZZ ZZZ satisfying the following equations:

x=X/ZZ y=Y/ZZZ ZZ^^{3}=ZZZ^^{2}

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

- 13.6M for addition: 12M+2S.
- 9.6M for addition with Z2=1: 8M+2S.
- 5.6M for addition with Z1=1 and Z2=1: 4M+2S.
- 13.6M for readdition: 12M+2S after 12M+2S.
- 9.6M for readdition with Z2=1: 8M+2S after 8M+2S.
- 5.6M for readdition with Z1=1 and Z2=1: 4M+2S after 4M+2S.
- 8.6M for doubling: 7M+2S.
- 6.4M for doubling with Z1=1: 4M+3S. 4M+3S.
- 103.8M for scaling: 1I+3M+1S.

- 13.34M for addition: 12M+2S.
- 9.34M for addition with Z2=1: 8M+2S.
- 5.34M for addition with Z1=1 and Z2=1: 4M+2S.
- 13.34M for readdition: 12M+2S after 12M+2S.
- 9.34M for readdition with Z2=1: 8M+2S after 8M+2S.
- 5.34M for readdition with Z1=1 and Z2=1: 4M+2S after 4M+2S.
- 8.34M for doubling: 7M+2S.
- 6.01M for doubling with Z1=1: 4M+3S. 4M+3S.
- 103.67M for scaling: 1I+3M+1S.

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

addition | ZZ1=1 and ZZZ1=1 and ZZ2=1 and ZZZ2=1 | 4M + 2S | 4M + 2S |

addition | ZZ2=1 and ZZZ2=1 | 8M + 2S | 8M + 2S |

addition | 12M + 2S | 12M + 2S | |

doubling | ZZ1=1 and ZZZ1=1 | 4M + 3S | |

doubling | ZZ1=1 and ZZZ1=1 | 4M + 3S | |

doubling | 7M + 2S | ||

doubling | 6M + 4S + 1*a | ||

scaling | 1I + 3M + 1S |

- Assumptions: ZZ1=1 and ZZZ1=1 and ZZ2=1 and ZZZ2=1.
- Cost: 4M + 2S + 6add + 1*2.
- Source: 2008 Sutherland.
- Explicit formulas:
P = X2-X1 R = Y2-Y1 PP = P^

^{2}PPP = P*PP Q = X1*PP X3 = R^^{2}-PPP-2*Q Y3 = R*(Q-X3)-Y1*PPP ZZ3 = PP ZZZ3 = PPP

- Assumptions: ZZ2=1 and ZZZ2=1.
- Cost: 8M + 2S + 6add + 1*2.
- Source: 2008 Sutherland.
- Explicit formulas:
U2 = X2*ZZ1 S2 = Y2*ZZZ1 P = U2-X1 R = S2-Y1 PP = P^

^{2}PPP = P*PP Q = X1*PP X3 = R^^{2}-PPP-2*Q Y3 = R*(Q-X3)-Y1*PPP ZZ3 = ZZ1*PP ZZZ3 = ZZZ1*PPP

- Cost: 12M + 2S + 6add + 1*2.
- Source: 2008 Sutherland.
- Explicit formulas:
U1 = X1*ZZ2 U2 = X2*ZZ1 S1 = Y1*ZZZ2 S2 = Y2*ZZZ1 P = U2-U1 R = S2-S1 PP = P^

^{2}PPP = P*PP Q = U1*PP X3 = R^^{2}-PPP-2*Q Y3 = R*(Q-X3)-S1*PPP ZZ3 = ZZ1*ZZ2*PP ZZZ3 = ZZZ1*ZZZ2*PPP

- Assumptions: ZZ1=1 and ZZZ1=1.
- Cost: 4M + 3S + 4add + 2*2 + 1*3.
- Source: 2008 Sutherland.
- Explicit formulas:
U = 2*Y1 V = U^

^{2}W = U*V S = X1*V M = 3*X1^^{2}+a X3 = M^^{2}-2*S Y3 = M*(S-X3)-W*Y1 ZZ3 = V ZZZ3 = W

- Assumptions: ZZ1=1 and ZZZ1=1.
- Cost: 4M + 3S + 4add + 2*2 + 1*3.
- Source: 2008 Sutherland.
- Explicit formulas:
U = 2*Y1 V = U^

^{2}W = U*V S = X1*V M = 3*(X1^^{2}-1) X3 = M^^{2}-2*S Y3 = M*(S-X3)-W*Y1 ZZ3 = V ZZZ3 = W

- Cost: 7M + 2S + 5add + 2*2 + 1*3.
- Source: 2008 Sutherland.
- Explicit formulas:
U = 2*Y1 V = U^

^{2}W = U*V S = X1*V M = 3*(X1-ZZ1)*(X1+ZZ1) X3 = M^^{2}-2*S Y3 = M*(S-X3)-W*Y1 ZZ3 = V*ZZ1 ZZZ3 = W*ZZZ1

- Cost: 6M + 4S + 1*a + 4add + 2*2 + 1*3.
- Source: 2008 Sutherland.
- Explicit formulas:
U = 2*Y1 V = U^

^{2}W = U*V S = X1*V M = 3*X1^^{2}+a*ZZ1^^{2}X3 = M^^{2}-2*S Y3 = M*(S-X3)-W*Y1 ZZ3 = V*ZZ1 ZZZ3 = W*ZZZ1

- Cost: 1I + 3M + 1S + 0add.
- Explicit formulas:
A = 1/ZZZ1 B = (ZZ1*A)^

^{2}X3 = X1*B Y3 = Y1*A ZZ3 = 1 ZZZ3 = 1