Genus-1 curves over large-characteristic fields

Edwards curves

x^^{2}+y^^{2}=c^^{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+1S. 10M+1S. 11M.
- 10M for addition with X2=1: 9M+1S.
- 9M for addition with Z2=1: 9M.
- 7M for addition with Z1=1 and Z2=1: 6M+1S.
- 11M for readdition: 10M+1S after 10M+1S. 10M+1S after 10M+1S. 10M+1S after 10M+1S. 11M after 11M. 9M+2S after 10M+3S.
- 10M for readdition with X2=1: 9M+1S after 9M+1S.
- 9M for readdition with Z2=1: 9M after 9M.
- 7M for readdition with Z1=1 and Z2=1: 6M+1S after 6M+1S.
- 7M for doubling: 3M+4S. 3M+4S. 3M+4S.
- 6M for doubling with Z1=1: 3M+3S.
- 13M for tripling: 9M+4S. 9M+4S.
- 102M for scaling: 1I+2M.

- 10.8M for addition: 10M+1S. 10M+1S. 10M+1S.
- 9.8M for addition with X2=1: 9M+1S.
- 9M for addition with Z2=1: 9M.
- 6.8M for addition with Z1=1 and Z2=1: 6M+1S.
- 10.6M for readdition: 9M+2S after 10M+3S.
- 9.8M for readdition with X2=1: 9M+1S after 9M+1S.
- 9M for readdition with Z2=1: 9M after 9M.
- 6.8M for readdition with Z1=1 and Z2=1: 6M+1S after 6M+1S.
- 6.2M for doubling: 3M+4S. 3M+4S. 3M+4S.
- 5.4M for doubling with Z1=1: 3M+3S.
- 12.2M for tripling: 9M+4S. 9M+4S.
- 102M for scaling: 1I+2M.

- 10.35M for addition: 7M+5S.
- 9.67M for addition with X2=1: 9M+1S.
- 9M for addition with Z2=1: 9M.
- 6.67M for addition with Z1=1 and Z2=1: 6M+1S.
- 10.34M for readdition: 9M+2S after 10M+3S.
- 9.67M for readdition with X2=1: 9M+1S after 9M+1S.
- 9M for readdition with Z2=1: 9M after 9M.
- 6.67M for readdition with Z1=1 and Z2=1: 6M+1S after 6M+1S.
- 5.68M for doubling: 3M+4S. 3M+4S. 3M+4S.
- 5.01M for doubling with Z1=1: 3M+3S.
- 11.68M for tripling: 9M+4S. 9M+4S.
- 102M for scaling: 1I+2M.

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

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

addition | k*c=1 and Z2=1 | 9M + 1*k | 9M + 1*k |

addition | X2=1 | 9M + 1S + 1*c + 1*d | 9M + 1S + 1*c + 1*d |

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

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

addition | c2=2*c and Z2=1 | 6M + 5S + 1*c2 + 1*d | 6M + 5S + 1*c2 + 1*d |

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

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

addition | i^^{2}=-1 |
10M + 1S + 3*i + 1*c + 1*d | 10M + 1S + 2*i + 1*c + 1*d |

addition | k*c=1 | 11M + 1*k | 11M + 1*k |

addition | c2=2*c | 7M + 5S + 1*c2 + 1*d | 7M + 5S + 1*c2 + 1*d |

addition | k*c=1 | 10M + 3S + 1*k | 9M + 2S + 1*k |

doubling | cc2=2*c*c and Z1=1 | 3M + 3S + 2*c | |

doubling | 3M + 4S + 3*c | ||

doubling | 3M + 4S + 3*c | ||

doubling | 3M + 4S + 3*c | ||

tripling | c2=2*c | 9M + 4S + 1*c2 | |

tripling | 9M + 4S + 1*c | ||

tripling | c=1 | 7M + 7S | |

tripling | cc4=4*c*c | 7M + 7S + 1*cc4 | |

scaling | 1I + 2M |

- Assumptions: Z1=1 and Z2=1.
- Cost: 6M + 1S + 1*c + 1*d + 8add.
- Cost: 6M + 1S + 1*c + 1*d + 7add dependent upon the first point.
- Source: 2007 Bernstein–Lange.
- 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-C) Z3 = c*(1-E^

^{2})

- Assumptions: k*c=1 and Z2=1.
- Cost: 9M + 1*k + 8add.
- Source: 2008.02.25 Hisil–Wong–Carter–Dawson, page 8.
- Explicit formulas:
A = X1 B = Y1 C = Z1*X2 D = Z1*Y2 E = A*B F = C*D G = E+F H = E-F J = (A-C)*(B+D)-H K = (A+D)*(B+C)-G X3 = G*J Y3 = H*K Z3 = k*J*K

- Assumptions: X2=1.
- Cost: 9M + 1S + 1*c + 1*d + 4add.
- Source: 2007 Hisil–Carter–Dawson.
- Strongly unified.
- Explicit formulas:
T0 = X1*Y2 T0 = T0+Y1 Y3 = Y1*Y2 T1 = Y3*X1 Y3 = Y3-X1 Z3 = Z1*Z2 X3 = T0*Z3 Y3 = Y3*Z3 T1 = d*T1 Z3 = Z3^

^{2}T0 = Z3-T1 Z3 = Z3+T1 X3 = X3*T0 Y3 = Y3*Z3 Z3 = Z3*T0 Z3 = c*Z3

- Assumptions: Z2=1.
- Cost: 9M + 1S + 1*c + 1*d + 7add.
- Cost: 9M + 1S + 1*c + 1*d + 6add dependent upon the first point.
- Source: 2007 Bernstein–Lange.
- Strongly unified.
- Explicit formulas:
R1 = X1 R2 = Y1 R3 = Z1 R4 = X2 R5 = Y2 R7 = R1+R2 R6 = R4+R5 R1 = R1*R4 R2 = R2*R5 R7 = R7*R6 R7 = R7-R1 R7 = R7-R2 R7 = R7*R3 R6 = R1*R2 R6 = d*R6 R2 = R2-R1 R2 = R2*R3 R3 = R3^

^{2}R1 = R3-R6 R3 = R3+R6 R2 = R2*R3 R3 = R3*R1 R1 = R1*R7 R3 = c*R3 X3 = R1 Y3 = R2 Z3 = R3

- Assumptions: Z2=1.
- Cost: 9M + 1S + 1*c + 1*d + 7add.
- Cost: 9M + 1S + 1*c + 1*d + 6add dependent upon the first point.
- Source: 2007 Bernstein–Lange.
- 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-C) Z3 = c*F*G

- Assumptions: c2=2*c and Z2=1.
- Cost: 6M + 5S + 1*c2 + 1*d + 13add + 1*2.
- Cost: 6M + 5S + 1*c2 + 1*d + 12add + 1*2 dependent upon the first point.
- Source: 2007 Bernstein–Lange.
- Strongly unified.
- Explicit formulas:
B = Z1^

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

- Cost: 10M + 1S + 1*c + 1*d + 7add.
- Cost: 10M + 1S + 1*c + 1*d + 6add dependent upon the first point.
- Source: 2007 Bernstein–Lange.
- Strongly unified.
- Explicit formulas:
R1 = X1 R2 = Y1 R3 = Z1 R4 = X2 R5 = Y2 R6 = Z2 R3 = R3*R6 R7 = R1+R2 R8 = R4+R5 R1 = R1*R4 R2 = R2*R5 R7 = R7*R8 R7 = R7-R1 R7 = R7-R2 R7 = R7*R3 R8 = R1*R2 R8 = d*R8 R2 = R2-R1 R2 = R2*R3 R3 = R3^

^{2}R1 = R3-R8 R3 = R3+R8 R2 = R2*R3 R3 = R3*R1 R1 = R1*R7 R3 = c*R3 X3 = R1 Y3 = R2 Z3 = R3

- Cost: 10M + 1S + 1*c + 1*d + 7add.
- Cost: 10M + 1S + 1*c + 1*d + 6add dependent upon the first point.
- Source: 2007 Bernstein–Lange.
- 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-C) Z3 = c*F*G

- Assumptions: i^
^{2}=-1. - Cost: 10M + 1S + 3*i + 1*c + 1*d + 9add + 2*2.
- Cost: 10M + 1S + 2*i + 1*c + 1*d + 7add + 2*2 dependent upon the first point.
- Source: 2007 Bernstein–Lange.
- Strongly unified.
- Explicit formulas:
iX2 = i*X2 C2 = Y2+iX2 D2 = Y2-iX2 iX1 = i*X1 C1 = Y1+iX1 D1 = Y1-iX1 A = Z1*Z2 B = 2*A^

^{2}C = C1*C2 D = D1*D2 L = D+C M = Y1*Y2 N = 2*M-L E = d*M*N F = B-E G = B+E X3 = i*A*F*(D-C) Y3 = A*G*L Z3 = c*G*F

- Assumptions: k*c=1.
- Cost: 11M + 1*k + 8add.
- Source: 2008.02.25 Hisil–Wong–Carter–Dawson, page 8.
- Explicit formulas:
A = X1*Z2 B = Y1*Z2 C = Z1*X2 D = Z1*Y2 E = A*B F = C*D G = E+F H = E-F J = (A-C)*(B+D)-H K = (A+D)*(B+C)-G X3 = G*J Y3 = H*K Z3 = k*J*K

- Assumptions: c2=2*c.
- Cost: 7M + 5S + 1*c2 + 1*d + 13add + 1*2.
- Cost: 7M + 5S + 1*c2 + 1*d + 12add + 1*2 dependent upon the first point.
- Source: 2007 Bernstein–Lange.
- Strongly unified.
- Explicit formulas:
A = Z1*Z2 B = A^

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

- Assumptions: k*c=1.
- Cost: 10M + 3S + 1*k + 13add + 2*2.
- Cost: 9M + 2S + 1*k + 13add + 2*2 dependent upon the first point.
- Source: 2009.03.11 Hisil–Wong–Carter–Dawson, after formula (17), plus denominator elimination.
- Explicit formulas:
R1 = X2*Y2 R2 = Z2^

^{2}A = X1*Y1 B = Z1^^{2}C = R2*A D = R1*B E = (X1-X2)*(Y1+Y2)-A+R1 F = (X1+Y2)*(Y1+X2)-A-R1 G = (Z1+Z2)^^{2}-B-R2 X3 = 2*E*(C+D) Y3 = 2*F*(C-D) Z3 = k*E*F*G

- Assumptions: cc2=2*c*c and Z1=1.
- Cost: 3M + 3S + 2*c + 5add.
- Source: 2007 Bernstein–Lange.
- Explicit formulas:
B = (X1+Y1)^

^{2}C = X1^^{2}D = Y1^^{2}E = C+D J = E-cc2 X3 = c*(B-E)*J Y3 = c*E*(C-D) Z3 = E*J

- Cost: 3M + 4S + 3*c + 5add + 1*2.
- Source: 2007 Bernstein–Lange; source comments that these formulas use two temporary registers.
- Explicit formulas:
R1 = X1 R2 = Y1 R3 = Z1 R4 = R1+R2 R3 = c*R3 R1 = R1^

^{2}R2 = R2^^{2}R3 = R3^^{2}R4 = R4^^{2}R3 = 2*R3 R5 = R1+R2 R2 = R1-R2 R4 = R4-R5 R3 = R5-R3 R1 = R3*R4 R3 = R3*R5 R2 = R2*R5 R1 = c*R1 R2 = c*R2 X3 = R1 Y3 = R2 Z3 = R3

- Cost: 3M + 4S + 3*c + 5add + 1*2.
- Source: 2007 Bernstein–Lange.
- Explicit formulas:
B = (X1+Y1)^

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

- Cost: 3M + 4S + 3*c + 5add + 2*2.
- Source: 2007 Bernstein–Lange; source comments that these formulas use one temporary register.
- Explicit formulas:
R1 = X1 R2 = Y1 R3 = Z1 R3 = c*R3 R4 = R1^

^{2}R1 = R1+R2 R1 = R1^^{2}R2 = R2^^{2}R3 = R3^^{2}R3 = 2*R3 R4 = R2+R4 R2 = 2*R2 R2 = R4-R2 R1 = R1-R4 R2 = R2*R4 R3 = R4-R3 R1 = R1*R3 R3 = R3*R4 R1 = c*R1 R2 = c*R2 X3 = R1 Y3 = R2 Z3 = R3

- Assumptions: c2=2*c.
- Cost: 9M + 4S + 1*c2 + 6add + 1*2.
- Source: 2007 Bernstein–Birkner–Lange–Peters.
- Explicit formulas:
XX = X1^

^{2}YY = Y1^^{2}ZZ = (c2*Z1)^^{2}D = XX+YY DD = D^^{2}H = 2*D*(XX-YY) P = DD-YY*ZZ Q = DD-XX*ZZ T = H+Q U = H-P X3 = P*U*X1 Y3 = Q*T*Y1 Z3 = T*U*Z1

- Cost: 9M + 4S + 1*c + 13add + 2*2.
- Source: 2007 Hisil–Carter–Dawson.
- Explicit formulas:
A = X1^

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

- Assumptions: c=1.
- Cost: 7M + 7S + 12add + 2*2 + 1*4.
- Source: 2007 Bernstein–Birkner–Lange–Peters.
- Explicit formulas:
XX = X1^

^{2}YY = Y1^^{2}ZZ = Z1^^{2}ZZ4 = 4*ZZ D = XX+YY DD = D^^{2}H = 2*D*(XX-YY) P = DD-YY*ZZ4 Q = DD-XX*ZZ4 T = H+Q TT = T^^{2}U = H-P X3 = 2*P*U*X1 Y3 = Q*((T+Y1)^^{2}-TT-YY) Z3 = U*((T+Z1)^^{2}-TT-ZZ)

- Assumptions: cc4=4*c*c.
- Cost: 7M + 7S + 1*cc4 + 12add + 2*2.
- Source: 2007 Bernstein–Birkner–Lange–Peters.
- Explicit formulas:
XX = X1^

^{2}YY = Y1^^{2}ZZ = Z1^^{2}ZZ4 = cc4*ZZ D = XX+YY DD = D^^{2}H = 2*D*(XX-YY) P = DD-YY*ZZ4 Q = DD-XX*ZZ4 T = H+Q TT = T^^{2}U = H-P X3 = 2*P*U*X1 Y3 = Q*((T+Y1)^^{2}-TT-YY) Z3 = U*((T+Z1)^^{2}-TT-ZZ)

- Cost: 1I + 2M + 0add.
- Explicit formulas:
A = 1/Z1 X3 = X1*A Y3 = Y1*A Z3 = 1