Genus-1 curves over large-characteristic fields

Twisted Edwards curves

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

Extended coordinates with a=-1 [database entry] make the additional assumptions

a=-1and represent x y as X Y Z T satisfying the following equations:

x=X/Z y=Y/Z x*y=T/Z

This representation was introduced in the Hisil–Wong–Carter–Dawson paper "Twisted Edwards curves revisited" (Asiacrypt 2008).

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

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

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

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

addition | Z1=1 and Z2=1 | 6M | 6M |

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

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

addition | Z2=1 and k=2*d | 7M + 1*k | 7M |

addition | Z2=1 | 7M | 7M |

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

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

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

addition | k=2*d | 8M + 1*k | 8M |

addition | 8M | 8M | |

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

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

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

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

- Assumptions: Z1=1 and Z2=1.
- Cost: 6M + 8add + 2*2.
- Cost: 6M + 6add + 1*2 dependent upon the first point.
- Source: 2008 Hisil–Wong–Carter–Dawson, http://eprint.iacr.org/2008/522, Section 3.2, plus assumption Z1=1.
- Explicit formulas:
A = (Y1-X1)*(Y2+X2) B = (Y1+X1)*(Y2-X2) C = 2*T2 D = 2*T1 E = D+C F = B-A G = B+A H = D-C X3 = E*F Y3 = G*H T3 = E*H Z3 = F*G

- Assumptions: Z1=1 and Z2=1 and k=2*d.
- Cost: 6M + 1S + 1*k + 9add.
- Cost: 6M + 1S + 7add dependent upon the first point.
- Source: 2008 Hisil–Wong–Carter–Dawson, http://eprint.iacr.org/2008/522, Section 3.1, plus assumption Z1=1, plus standard simplification.
- Strongly unified.
- Explicit formulas:
A = (Y1-X1)*(Y2-X2) B = (Y1+X1)*(Y2+X2) C = T1*k*T2 E = B-A F = 2-C G = 2+C H = B+A X3 = E*F Y3 = G*H T3 = E*H Z3 = 4-C^

^{2}

- Assumptions: Z1=1 and Z2=1.
- Cost: 7M + 1*a + 7add.
- Cost: 7M + 1*a + 6add dependent upon the first point.
- Source: 2008 Hisil–Wong–Carter–Dawson, http://eprint.iacr.org/2008/522, Section 3.2, plus assumption Z1=1.
- Explicit formulas:
A = X1*X2 B = Y1*Y2 C = T2 D = T1 E = D+C F = (X1-Y1)*(X2+Y2)+B-A G = B+a*A H = D-C X3 = E*F Y3 = G*H T3 = E*H Z3 = F*G

- Assumptions: Z2=1 and k=2*d.
- Cost: 7M + 1*k + 8add + 1*2.
- Cost: 7M + 6add + 1*2 dependent upon the first point.
- Source: 2008 Hisil–Wong–Carter–Dawson, http://eprint.iacr.org/2008/522, Section 3.1.
- Strongly unified.
- Explicit formulas:
A = (Y1-X1)*(Y2-X2) B = (Y1+X1)*(Y2+X2) C = T1*k*T2 D = 2*Z1 E = B-A F = D-C G = D+C H = B+A X3 = E*F Y3 = G*H T3 = E*H Z3 = F*G

- Assumptions: Z2=1.
- Cost: 7M + 8add + 2*2.
- Cost: 7M + 6add + 1*2 dependent upon the first point.
- Source: 2008 Hisil–Wong–Carter–Dawson, http://eprint.iacr.org/2008/522, Section 3.2.
- Explicit formulas:
A = (Y1-X1)*(Y2+X2) B = (Y1+X1)*(Y2-X2) C = Z1*2*T2 D = 2*T1 E = D+C F = B-A G = B+A H = D-C X3 = E*F Y3 = G*H T3 = E*H Z3 = F*G

- Assumptions: Z1=1 and Z2=1.
- Cost: 7M + 1S + 1*a + 1*d + 8add.
- Cost: 7M + 1S + 1*a + 7add dependent upon the first point.
- Source: 2008 Hisil–Wong–Carter–Dawson, http://eprint.iacr.org/2008/522, Section 3.1, plus assumption Z1=1, plus standard simplification.
- Strongly unified.
- Explicit formulas:
A = X1*X2 B = Y1*Y2 C = T1*d*T2 E = (X1+Y1)*(X2+Y2)-A-B F = 1-C G = 1+C H = B-a*A X3 = E*F Y3 = G*H T3 = E*H Z3 = 1-C^

^{2}

- Assumptions: Z2=1.
- Cost: 8M + 1*a + 7add.
- Cost: 8M + 1*a + 6add dependent upon the first point.
- Source: 2008 Hisil–Wong–Carter–Dawson, http://eprint.iacr.org/2008/522, Section 3.2.
- Explicit formulas:
A = X1*X2 B = Y1*Y2 C = Z1*T2 D = T1 E = D+C F = (X1-Y1)*(X2+Y2)+B-A G = B+a*A H = D-C X3 = E*F Y3 = G*H T3 = E*H Z3 = F*G

- Assumptions: Z2=1.
- Cost: 8M + 1*a + 1*d + 7add.
- Cost: 8M + 1*a + 6add dependent upon the first point.
- Source: 2008 Hisil–Wong–Carter–Dawson, http://eprint.iacr.org/2008/522, Section 3.1.
- Strongly unified.
- Explicit formulas:
A = X1*X2 B = Y1*Y2 C = T1*d*T2 D = Z1 E = (X1+Y1)*(X2+Y2)-A-B F = D-C G = D+C H = B-a*A X3 = E*F Y3 = G*H T3 = E*H Z3 = F*G

- Assumptions: k=2*d.
- Cost: 8M + 1*k + 8add + 1*2.
- Cost: 8M + 6add dependent upon the first point.
- Source: 2008 Hisil–Wong–Carter–Dawson, http://eprint.iacr.org/2008/522, Section 3.1.
- Strongly unified.
- Explicit formulas:
A = (Y1-X1)*(Y2-X2) B = (Y1+X1)*(Y2+X2) C = T1*k*T2 D = Z1*2*Z2 E = B-A F = D-C G = D+C H = B+A X3 = E*F Y3 = G*H T3 = E*H Z3 = F*G

- Cost: 8M + 8add + 2*2.
- Cost: 8M + 6add dependent upon the first point.
- Source: 2008 Hisil–Wong–Carter–Dawson, http://eprint.iacr.org/2008/522, Section 3.2.
- Explicit formulas:
A = (Y1-X1)*(Y2+X2) B = (Y1+X1)*(Y2-X2) C = Z1*2*T2 D = T1*2*Z2 E = D+C F = B-A G = B+A H = D-C X3 = E*F Y3 = G*H T3 = E*H Z3 = F*G

- Cost: 9M + 1*a + 7add.
- Cost: 9M + 1*a + 6add dependent upon the first point.
- Source: 2008 Hisil–Wong–Carter–Dawson, http://eprint.iacr.org/2008/522, Section 3.2.
- Explicit formulas:
A = X1*X2 B = Y1*Y2 C = Z1*T2 D = T1*Z2 E = D+C F = (X1-Y1)*(X2+Y2)+B-A G = B+a*A H = D-C X3 = E*F Y3 = G*H T3 = E*H Z3 = F*G

- Cost: 9M + 1*a + 1*d + 7add.
- Cost: 9M + 1*a + 6add dependent upon the first point.
- Source: 2008 Hisil–Wong–Carter–Dawson, http://eprint.iacr.org/2008/522, Section 3.1.
- Strongly unified.
- Explicit formulas:
A = X1*X2 B = Y1*Y2 C = T1*d*T2 D = Z1*Z2 E = (X1+Y1)*(X2+Y2)-A-B F = D-C G = D+C H = B-a*A X3 = E*F Y3 = G*H T3 = E*H Z3 = F*G

- Assumptions: Z1=1.
- Cost: 3M + 4S + 1*a + 7add + 1*2.
- Source: 2008 Hisil–Wong–Carter–Dawson, http://eprint.iacr.org/2008/522, Section 3.3, plus assumption Z1=1, plus standard simplification.
- Explicit formulas:
A = X1^

^{2}B = Y1^^{2}D = a*A E = (X1+Y1)^^{2}-A-B G = D+B H = D-B X3 = E*(G-2) Y3 = G*H T3 = E*H Z3 = G^^{2}-2*G

- Cost: 4M + 4S + 1*a + 6add + 1*2.
- Source: 2008 Hisil–Wong–Carter–Dawson, http://eprint.iacr.org/2008/522, Section 3.3.
- Explicit formulas:
A = X1^

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