Genus-1 curves over large-characteristic fields

Twisted Edwards curves

a*x^^{2}+y^^{2}=1+d*x^^{2}*y^^{2}

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

x=X/Z y=Y/Z

- 11M for addition: 10M+1S.
- 10M for addition with Z2=1: 9M+1S.
- 7M for addition with Z1=1 and Z2=1: 6M+1S.
- 11M for readdition: 10M+1S after 10M+1S.
- 10M for readdition with Z2=1: 9M+1S after 9M+1S.
- 7M for readdition with Z1=1 and Z2=1: 6M+1S after 6M+1S.
- 7M for doubling: 3M+4S.
- 6M for doubling with Z1=1: 2M+4S.
- 12M for tripling: 9M+3S.

- 10.8M for addition: 10M+1S.
- 9.8M for addition with Z2=1: 9M+1S.
- 6.8M for addition with Z1=1 and Z2=1: 6M+1S.
- 10.8M for readdition: 10M+1S after 10M+1S.
- 9.8M for readdition with Z2=1: 9M+1S after 9M+1S.
- 6.8M for readdition with Z1=1 and Z2=1: 6M+1S after 6M+1S.
- 6.2M for doubling: 3M+4S.
- 5.2M for doubling with Z1=1: 2M+4S.
- 11.4M for tripling: 9M+3S.

- 10.67M for addition: 10M+1S.
- 9.67M for addition with Z2=1: 9M+1S.
- 6.67M for addition with Z1=1 and Z2=1: 6M+1S.
- 10.67M for readdition: 10M+1S after 10M+1S.
- 9.67M for readdition with Z2=1: 9M+1S after 9M+1S.
- 6.67M for readdition with Z1=1 and Z2=1: 6M+1S after 6M+1S.
- 5.68M for doubling: 3M+4S.
- 4.68M for doubling with Z1=1: 2M+4S.
- 11.01M for tripling: 9M+3S.

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

addition | Z1=1 and Z2=1 | 6M + 1S + 1*a + 1*d | 6M + 1S + 1*a + 1*d |

addition | Z2=1 | 9M + 1S + 1*a + 1*d | 9M + 1S + 1*a + 1*d |

addition | 10M + 1S + 1*a + 1*d | 10M + 1S + 1*a + 1*d | |

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

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

tripling | 9M + 3S + 1*a |

- Assumptions: Z1=1 and Z2=1.
- Cost: 6M + 1S + 1*a + 1*d + 8add.
- Cost: 6M + 1S + 1*a + 1*d + 7add dependent upon the first point.
- Source: 2008 Bernstein–Birkner–Joye–Lange–Peters http://eprint.iacr.org/2008/013 Section 6, plus Z2=1, plus Z1=1, plus standard simplification.
- Strongly unified.
- Explicit formulas:
C = X1*X2 D = Y1*Y2 E = d*C*D X3 = (1-E)*((X1+Y1)*(X2+Y2)-C-D) Y3 = (1+E)*(D-a*C) Z3 = 1-E^

^{2}

- Assumptions: Z2=1.
- Cost: 9M + 1S + 1*a + 1*d + 7add.
- Cost: 9M + 1S + 1*a + 1*d + 6add dependent upon the first point.
- Source: 2008 Bernstein–Birkner–Joye–Lange–Peters http://eprint.iacr.org/2008/013 Section 6, plus Z2=1, plus common-subexpression elimination.
- Strongly unified.
- Explicit formulas:
B = Z1^

^{2}C = X1*X2 D = Y1*Y2 E = d*C*D F = B-E G = B+E X3 = Z1*F*((X1+Y1)*(X2+Y2)-C-D) Y3 = Z1*G*(D-a*C) Z3 = F*G

- Cost: 10M + 1S + 1*a + 1*d + 7add.
- Cost: 10M + 1S + 1*a + 1*d + 6add dependent upon the first point.
- Source: 2008 Bernstein–Birkner–Joye–Lange–Peters http://eprint.iacr.org/2008/013 Section 6.
- Strongly unified.
- Explicit formulas:
A = Z1*Z2 B = A^

^{2}C = X1*X2 D = Y1*Y2 E = d*C*D F = B-E G = B+E X3 = A*F*((X1+Y1)*(X2+Y2)-C-D) Y3 = A*G*(D-a*C) Z3 = F*G

- Assumptions: Z1=1.
- Cost: 2M + 4S + 1*a + 7add + 1*2.
- Source: 2008 Bernstein–Birkner–Joye–Lange–Peters http://eprint.iacr.org/2008/013, plus Z1=1, plus standard simplification.
- Explicit formulas:
B = (X1+Y1)^

^{2}C = X1^^{2}D = Y1^^{2}E = a*C F = E+D X3 = (B-C-D)*(F-2) Y3 = F*(E-D) Z3 = F^^{2}-2*F

- Cost: 3M + 4S + 1*a + 6add + 1*2.
- Source: 2008 Bernstein–Birkner–Joye–Lange–Peters http://eprint.iacr.org/2008/013.
- Explicit formulas:
B = (X1+Y1)^

^{2}C = X1^^{2}D = Y1^^{2}E = a*C F = E+D H = Z1^^{2}J = F-2*H X3 = (B-C-D)*J Y3 = F*(E-D) Z3 = F*J

- Cost: 9M + 3S + 1*a + 7add + 2*2.
- Source: 2015 Chuengsatiansup.
- Explicit formulas:
YY = Y1^

^{2}aXX = a*X1^^{2}Ap = YY+aXX B = 2*(2*Z1^^{2}-Ap) xB = aXX*B yB = YY*B AA = Ap*(YY-aXX) F = AA-yB G = AA+xB X3 = X1*(yB+AA)*F Y3 = Y1*(xB-AA)*G Z3 = Z1*F*G