Genus-1 curves over large-characteristic fields

Twisted Edwards curves

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

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

x=Z/X y=Z/Y

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

- 9.8M for addition: 9M+1S.
- 8.8M for addition with Z2=1: 8M+1S.
- 7M for addition with Z1=1 and Z2=1: 7M.
- 9.8M for readdition: 9M+1S after 9M+1S.
- 8.8M for readdition with Z2=1: 8M+1S after 8M+1S.
- 7M for readdition with Z1=1 and Z2=1: 7M after 7M.
- 6.2M for doubling: 3M+4S.
- 5.4M for doubling with Z1=1: 3M+3S.

- 9.67M for addition: 9M+1S.
- 8.67M for addition with Z2=1: 8M+1S.
- 7M for addition with Z1=1 and Z2=1: 7M.
- 9.67M for readdition: 9M+1S after 9M+1S.
- 8.67M for readdition with Z2=1: 8M+1S after 8M+1S.
- 7M for readdition with Z1=1 and Z2=1: 7M after 7M.
- 5.68M for doubling: 3M+4S.
- 5.01M for doubling with Z1=1: 3M+3S.

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

addition | Z1=1 and Z2=1 | 7M + 1*a | 7M + 1*a |

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

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

doubling | Z1=1 and d2=2*d | 3M + 3S + 1*a | |

doubling | d2=2*d | 3M + 4S + 1*a + 1*d2 |

- Assumptions: Z1=1 and Z2=1.
- Cost: 7M + 1*a + 7add.
- Cost: 7M + 1*a + 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 Z1=1, plus common-subexpression elimination.
- Strongly unified.
- Explicit formulas:
C = X1*X2 D = Y1*Y2 E = C*D H = C-a*D I = (X1+Y1)*(X2+Y2)-C-D X3 = (E+d)*H Y3 = (E-d)*I Z3 = H*I

- Assumptions: Z2=1.
- Cost: 8M + 1S + 1*a + 1*d + 7add.
- Cost: 8M + 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 = d*Z1^

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

- 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.
- Strongly unified.
- Explicit formulas:
A = Z1*Z2 B = d*A^

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

- Assumptions: Z1=1 and d2=2*d.
- Cost: 3M + 3S + 1*a + 6add.
- Source: 2008 Bernstein–Birkner–Joye–Lange–Peters http://eprint.iacr.org/2008/013, Section 6, plus Z1=1.
- Explicit formulas:
A = X1^

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

- Assumptions: d2=2*d.
- Cost: 3M + 4S + 1*a + 1*d2 + 6add.
- Source: 2008 Bernstein–Birkner–Joye–Lange–Peters http://eprint.iacr.org/2008/013, Section 6.
- Explicit formulas:
A = X1^

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