Genus-1 curves over large-characteristic fields

Edwards curves

x^^{2}+y^^{2}=c^^{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

This representation was introduced in the Bernstein–Lange paper "Inverted Edwards coordinates" (AAECC 2007). This representation does not cover the points (0,+-c) and (+-c,0).

- 10M for addition: 9M+1S.
- 9M for addition with Z2=1: 8M+1S. 9M.
- 9M for addition with X2=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. 9M after 9M.
- 9M for readdition with X2=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.
- 13M for tripling: 9M+4S.
- 102M for scaling: 1I+2M.

- 9.8M for addition: 9M+1S.
- 8.8M for addition with Z2=1: 8M+1S.
- 8.8M for addition with X2=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.
- 8.8M for readdition with X2=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.
- 12.2M for tripling: 9M+4S.
- 102M for scaling: 1I+2M.

- 9.67M for addition: 9M+1S.
- 8.67M for addition with Z2=1: 8M+1S.
- 8.67M for addition with X2=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.
- 8.67M for readdition with X2=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.
- 11.68M for tripling: 9M+4S.
- 102M for scaling: 1I+2M.

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

addition | Z1=1 and Z2=1 | 7M + 2*c | 7M + 2*c |

addition | X2=1 | 8M + 1S + 2*c + 1*d | 8M + 1S + 2*c + 1*d |

addition | Z2=1 | 8M + 1S + 2*c + 1*d | 8M + 1S + 2*c + 1*d |

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

addition | 9M + 1S + 2*c + 1*d | 9M + 1S + 2*c + 1*d | |

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

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

doubling | ccd2=2*c*c*d | 3M + 4S + 1*ccd2 + 1*c | |

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

tripling | ccd=c*c*d | 7M + 7S + 1*ccd | |

scaling | 1I + 2M |

- Assumptions: Z1=1 and Z2=1.
- Cost: 7M + 2*c + 7add.
- Cost: 7M + 2*c + 6add dependent upon the first point.
- Source: 2007 Bernstein–Lange.
- Strongly unified.
- Explicit formulas:
C = X1*X2 D = Y1*Y2 E = C*D H = C-D I = (X1+Y1)*(X2+Y2)-C-D X3 = c*(E+d)*H Y3 = c*(E-d)*I Z3 = H*I

- Assumptions: X2=1.
- Cost: 8M + 1S + 2*c + 1*d + 4add.
- Source: 2007 Bernstein–Lange.
- Strongly unified.
- Explicit formulas:
A = Z1*Z2 B = d*A^

^{2}D = Y1*Y2 E = X1*D F = E-B G = E+B H = X1-D I = X1*Y2+Y1 X3 = c*G*H Y3 = c*F*I Z3 = A*H*I

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

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

- Assumptions: Z2=1.
- Cost: 9M + 1*c + 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 X3 = ((A+D)*(B+C)-G)*H Y3 = ((A-C)*(B+D)-H)*G Z3 = c*G*H

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

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

- Cost: 11M + 1*c + 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 X3 = ((A+D)*(B+C)-G)*H Y3 = ((A-C)*(B+D)-H)*G Z3 = c*G*H

- Assumptions: ccd2=2*c*c*d and Z1=1.
- Cost: 3M + 3S + 1*c + 5add.
- Source: 2007 Bernstein–Lange.
- Explicit formulas:
A = X1^

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

- Assumptions: ccd2=2*c*c*d.
- Cost: 3M + 4S + 1*ccd2 + 1*c + 5add.
- Source: 2007 Bernstein–Lange.
- Explicit formulas:
A = X1^

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

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

^{2}YY = Y1^^{2}ZZ = (c*Z1)^^{2}D = XX+YY DD = D^^{2}E = 4*(D-d*ZZ) H = 2*D*(YY-XX) P = DD-XX*E Q = DD-YY*E X3 = (H+Q)*Q*X1 Y3 = (H-P)*P*Y1 Z3 = P*Q*Z1

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

^{2}YY = Y1^^{2}ZZ = Z1^^{2}D = XX+YY DD = D^^{2}E = 4*(D-ccd*ZZ) H = 2*D*(YY-XX) P = DD-XX*E Q = DD-YY*E QQ = Q^^{2}X3 = (H+Q)*((Q+X1)^^{2}-QQ-XX) Y3 = 2*(H-P)*P*Y1 Z3 = P*((Q+Z1)^^{2}-QQ-ZZ)

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