Genus-1 curves over large-characteristic fields

Edwards curves

x^^{2}+y^^{2}=c^^{2}*(1+d*x^^{2}*y^^{2})

YZ coordinates with square d [database entry] make the additional assumptions

c=1 d=r^and represent x y as Y Z satisfying the following equations:^{2}

r*y=Y/Z

The following formulas are the outcome of a discussion in 2009 among Daniel J. Bernstein, David Kohel, and Tanja Lange. The core ideas were published by Pierrick Gaudry in 2006.

- 4M for doubling: 4S.
- 2M for doubling with Z1=1: 2S.
- 8M for differential addition: 4M+4S.
- 7M for differential addition with Z1=1: 3M+4S.
- 10M for differential addition and doubling: 4M+6S.
- 9M for differential addition and doubling with Z1=1: 3M+6S.
- 101M for scaling: 1I+1M.

- 3.2M for doubling: 4S.
- 1.6M for doubling with Z1=1: 2S.
- 7.2M for differential addition: 4M+4S.
- 6.2M for differential addition with Z1=1: 3M+4S.
- 8.8M for differential addition and doubling: 4M+6S.
- 7.8M for differential addition and doubling with Z1=1: 3M+6S.
- 101M for scaling: 1I+1M.

- 2.68M for doubling: 4S.
- 1.34M for doubling with Z1=1: 2S.
- 6.68M for differential addition: 4M+4S.
- 5.68M for differential addition with Z1=1: 3M+4S.
- 8.02M for differential addition and doubling: 4M+6S.
- 7.02M for differential addition and doubling with Z1=1: 3M+6S.
- 101M for scaling: 1I+1M.

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

doubling | s=(1+r)/(1-r) and r2=2*r and Z1=1 | 2S + 1*r2 + 1*s | |

doubling | s=(1+r)/(1-r) and Z1=1 | 3S + 1*s | |

doubling | s=(1+r)/(1-r) | 4S + 1*r + 1*s | |

doubling | s=(1+r)/(1-r) | 6S + 2*r + 1*s | |

diffadd | s=(1+r)/(1-r) and Z1=1 | 3M + 4S + 3*r + 1*s | |

diffadd | s=(1+r)/(1-r) | 4M + 4S + 3*r + 1*s | |

diffadd | s=(1+r)/(1-r) | 4M + 8S + 5*r + 1*s | |

ladder | s=(1+r)/(1-r) and Z1=1 | 3M + 6S + 3*r + 2*s | |

ladder | s=(1+r)/(1-r) | 4M + 6S + 3*r + 2*s | |

ladder | s=(1+r)/(1-r) | 4M + 14S + 7*r + 2*s | |

scaling | 1I + 1M |

- Assumptions: s=(1+r)/(1-r) and r2=2*r and Z1=1.
- Cost: 2S + 1*r2 + 1*s + 5add.
- Source: 2006 Gaudry "Variants of the Montgomery form based on Theta functions", page 22/52, with A^
^{2}/B^^{2}= (a^^{2}+b^^{2})/(a^^{2}-b^^{2}) as on page 20/52, replacing incorrect B^^{2}/A^^{2}and b/a on page 22/52 with correct A^^{2}/B^^{2}and a/b; or 2009 Gaudry–Lubicz "The arithmetic of characteristic 2 Kummer surfaces and of elliptic Kummer lines", Section 6.2, replacing incorrect A'/B' = (a^^{2}+b^^{2})/(a^^{2}-b^^{2}) with correct A'^^{2}/B'^^{2}= (a^^{2}+b^^{2})/(a^^{2}-b^^{2}), replacing A'^^{2}/B'^^{2}with A^^{2}/B^^{2}, and replacing z... with y...; plus notation changes: a/b and A^^{2}/B^^{2}defined as 1/sqrt(r) and (1+r)/(1-r), input x^^{2}/y^^{2}replaced by r Z1^^{2}/Y1^^{2}, intermediate x'/y' replaced by W/V, output X/Y replaced by sqrt(r) Z3/Y3; plus common-subexpression elimination; plus assumption Z1=1; plus standard simplification. - Explicit formulas:
YY = Y1^

^{2}A = r2*YY B = d+YY^^{2}V = s*(B-A) W = B+A Y3 = W-V Z3 = W+V

- Assumptions: s=(1+r)/(1-r) and Z1=1.
- Cost: 3S + 1*s + 5add + 1*2.
- Source: 2006 Gaudry "Variants of the Montgomery form based on Theta functions", page 22/52, with A^
^{2}/B^^{2}= (a^^{2}+b^^{2})/(a^^{2}-b^^{2}) as on page 20/52, replacing incorrect B^^{2}/A^^{2}and b/a on page 22/52 with correct A^^{2}/B^^{2}and a/b; or 2009 Gaudry–Lubicz "The arithmetic of characteristic 2 Kummer surfaces and of elliptic Kummer lines", Section 6.2, replacing incorrect A'/B' = (a^^{2}+b^^{2})/(a^^{2}-b^^{2}) with correct A'^^{2}/B'^^{2}= (a^^{2}+b^^{2})/(a^^{2}-b^^{2}), replacing A'^^{2}/B'^^{2}with A^^{2}/B^^{2}, and replacing z... with y...; plus notation changes: a/b and A^^{2}/B^^{2}defined as 1/sqrt(r) and (1+r)/(1-r), input x^^{2}/y^^{2}replaced by r Z1^^{2}/Y1^^{2}, intermediate x'/y' replaced by W/V, output X/Y replaced by sqrt(r) Z3/Y3; plus common-subexpression elimination; plus assumption Z1=1; plus standard simplification. - Explicit formulas:
YY = Y1^

^{2}B = d+YY^^{2}W = (r+YY)^^{2}V = s*(2*B-W) Y3 = W-V Z3 = W+V

- Assumptions: s=(1+r)/(1-r).
- Cost: 4S + 1*r + 1*s + 4add.
- Source: 2006 Gaudry "Variants of the Montgomery form based on Theta functions", page 22/52, with A^
^{2}/B^^{2}= (a^^{2}+b^^{2})/(a^^{2}-b^^{2}) as on page 20/52, replacing incorrect B^^{2}/A^^{2}and b/a on page 22/52 with correct A^^{2}/B^^{2}and a/b; or 2009 Gaudry–Lubicz "The arithmetic of characteristic 2 Kummer surfaces and of elliptic Kummer lines", Section 6.2, replacing incorrect A'/B' = (a^^{2}+b^^{2})/(a^^{2}-b^^{2}) with correct A'^^{2}/B'^^{2}= (a^^{2}+b^^{2})/(a^^{2}-b^^{2}), replacing A'^^{2}/B'^^{2}with A^^{2}/B^^{2}, and replacing z... with y...; plus notation changes: a/b and A^^{2}/B^^{2}defined as 1/sqrt(r) and (1+r)/(1-r), input x^^{2}/y^^{2}replaced by r Z1^^{2}/Y1^^{2}, intermediate x'/y' replaced by W/V, output X/Y replaced by sqrt(r) Z3/Y3; plus common-subexpression elimination. - Explicit formulas:
YY = Y1^

^{2}ZZ = r*Z1^^{2}V = s*(ZZ-YY)^^{2}W = (ZZ+YY)^^{2}Y3 = W-V Z3 = W+V

- Assumptions: s=(1+r)/(1-r).
- Cost: 6S + 2*r + 1*s + 4add.
- Source: 2006 Gaudry "Variants of the Montgomery form based on Theta functions", page 22/52, with A^
^{2}/B^^{2}= (a^^{2}+b^^{2})/(a^^{2}-b^^{2}) as on page 20/52, replacing incorrect B^^{2}/A^^{2}and b/a on page 22/52 with correct A^^{2}/B^^{2}and a/b; or 2009 Gaudry–Lubicz "The arithmetic of characteristic 2 Kummer surfaces and of elliptic Kummer lines", Section 6.2, replacing incorrect A'/B' = (a^^{2}+b^^{2})/(a^^{2}-b^^{2}) with correct A'^^{2}/B'^^{2}= (a^^{2}+b^^{2})/(a^^{2}-b^^{2}), replacing A'^^{2}/B'^^{2}with A^^{2}/B^^{2}, and replacing z... with y...; plus notation changes: a/b and A^^{2}/B^^{2}defined as 1/sqrt(r) and (1+r)/(1-r), input x^^{2}/y^^{2}replaced by r Z1^^{2}/Y1^^{2}, intermediate x'/y' replaced by W/V, output X/Y replaced by sqrt(r) Z3/Y3. - Explicit formulas:
V = s*(r*Z1^

^{2}-Y1^^{2})^^{2}W = (r*Z1^^{2}+Y1^^{2})^^{2}Y3 = W-V Z3 = W+V

- Assumptions: s=(1+r)/(1-r) and Z1=1.
- Cost: 3M + 4S + 3*r + 1*s + 6add.
- Source: 2006 Gaudry "Variants of the Montgomery form based on Theta functions", page 23/52, with A^
^{2}/B^^{2}= (a^^{2}+b^^{2})/(a^^{2}-b^^{2}) as on page 20/52, replacing incorrect B^^{2}/A^^{2}on page 23/52 with correct A^^{2}/B^^{2}and a/b; or 2009 Gaudry–Lubicz "The arithmetic of characteristic 2 Kummer surfaces and of elliptic Kummer lines", Section 6.2, replacing incorrect A'/B' = (a^^{2}+b^^{2})/(a^^{2}-b^^{2}) with correct A'^^{2}/B'^^{2}= (a^^{2}+b^^{2})/(a^^{2}-b^^{2}), replacing A'^^{2}/B'^^{2}with A^^{2}/B^^{2}, and replacing z... with y...; plus notation changes: a/b and A^^{2}/B^^{2}defined as 1/sqrt(r) and (1+r)/(1-r), input x^^{2}/y^^{2}etc. replaced by r Z2^^{2}/Y2^^{2}and r Z3^^{2}/Y3^^{2}and r Z1^^{2}/Y1^^{2}, intermediate x'/y' replaced by W/V, output X/Y replaced by sqrt(r) Z5/Y5; plus common-subexpression elimination; plus assumption Z1=1. - Explicit formulas:
YY2 = Y2^

^{2}ZZ2 = r*Z2^^{2}YY3 = Y3^^{2}ZZ3 = r*Z3^^{2}V = s*(ZZ2-YY2)*(ZZ3-YY3) W = (ZZ2+YY2)*(ZZ3+YY3) Y5 = r*(W-V) Z5 = Y1*(W+V)

- Assumptions: s=(1+r)/(1-r).
- Cost: 4M + 4S + 3*r + 1*s + 6add.
- Source: 2006 Gaudry "Variants of the Montgomery form based on Theta functions", page 23/52, with A^
^{2}/B^^{2}= (a^^{2}+b^^{2})/(a^^{2}-b^^{2}) as on page 20/52, replacing incorrect B^^{2}/A^^{2}on page 23/52 with correct A^^{2}/B^^{2}and a/b; or 2009 Gaudry–Lubicz "The arithmetic of characteristic 2 Kummer surfaces and of elliptic Kummer lines", Section 6.2, replacing incorrect A'/B' = (a^^{2}+b^^{2})/(a^^{2}-b^^{2}) with correct A'^^{2}/B'^^{2}= (a^^{2}+b^^{2})/(a^^{2}-b^^{2}), replacing A'^^{2}/B'^^{2}with A^^{2}/B^^{2}, and replacing z... with y...; plus notation changes: a/b and A^^{2}/B^^{2}defined as 1/sqrt(r) and (1+r)/(1-r), input x^^{2}/y^^{2}etc. replaced by r Z2^^{2}/Y2^^{2}and r Z3^^{2}/Y3^^{2}and r Z1^^{2}/Y1^^{2}, intermediate x'/y' replaced by W/V, output X/Y replaced by sqrt(r) Z5/Y5; plus common-subexpression elimination. - Explicit formulas:
YY2 = Y2^

^{2}ZZ2 = r*Z2^^{2}YY3 = Y3^^{2}ZZ3 = r*Z3^^{2}V = s*(ZZ2-YY2)*(ZZ3-YY3) W = (ZZ2+YY2)*(ZZ3+YY3) Y5 = (r*Z1)*(W-V) Z5 = Y1*(W+V)

- Assumptions: s=(1+r)/(1-r).
- Cost: 4M + 8S + 5*r + 1*s + 6add.
- Source: 2006 Gaudry "Variants of the Montgomery form based on Theta functions", page 23/52, with A^
^{2}/B^^{2}= (a^^{2}+b^^{2})/(a^^{2}-b^^{2}) as on page 20/52, replacing incorrect B^^{2}/A^^{2}on page 23/52 with correct A^^{2}/B^^{2}and a/b; or 2009 Gaudry–Lubicz "The arithmetic of characteristic 2 Kummer surfaces and of elliptic Kummer lines", Section 6.2, replacing incorrect A'/B' = (a^^{2}+b^^{2})/(a^^{2}-b^^{2}) with correct A'^^{2}/B'^^{2}= (a^^{2}+b^^{2})/(a^^{2}-b^^{2}), replacing A'^^{2}/B'^^{2}with A^^{2}/B^^{2}, and replacing z... with y...; plus notation changes: a/b and A^^{2}/B^^{2}defined as 1/sqrt(r) and (1+r)/(1-r), input x^^{2}/y^^{2}etc. replaced by r Z2^^{2}/Y2^^{2}and r Z3^^{2}/Y3^^{2}and r Z1^^{2}/Y1^^{2}, intermediate x'/y' replaced by W/V, output X/Y replaced by sqrt(r) Z5/Y5. - Explicit formulas:
V = s*(r*Z2^

^{2}-Y2^^{2})*(r*Z3^^{2}-Y3^^{2}) W = (r*Z2^^{2}+Y2^^{2})*(r*Z3^^{2}+Y3^^{2}) Y5 = r*Z1*(W-V) Z5 = Y1*(W+V)

- Assumptions: s=(1+r)/(1-r) and Z1=1.
- Cost: 3M + 6S + 3*r + 2*s + 8add.
- Source: 2006 Gaudry "Variants of the Montgomery form based on Theta functions", pages 22/52 and 23/52, with A^
^{2}/B^^{2}= (a^^{2}+b^^{2})/(a^^{2}-b^^{2}) as on page 20/52, replacing incorrect B^^{2}/A^^{2}and b/a on pages 22/52 and 23/52 with correct A^^{2}/B^^{2}and a/b; or 2009 Gaudry–Lubicz "The arithmetic of characteristic 2 Kummer surfaces and of elliptic Kummer lines", Section 6.2, replacing incorrect A'/B' = (a^^{2}+b^^{2})/(a^^{2}-b^^{2}) with correct A'^^{2}/B'^^{2}= (a^^{2}+b^^{2})/(a^^{2}-b^^{2}), replacing A'^^{2}/B'^^{2}with A^^{2}/B^^{2}, and replacing z... with y...; plus notation changes: a/b and A^^{2}/B^^{2}defined as 1/sqrt(r) and (1+r)/(1-r), input x^^{2}/y^^{2}etc. replaced by r Z2^^{2}/Y2^^{2}and r Z3^^{2}/Y3^^{2}and r Z1^^{2}/Y1^^{2}, intermediate x'/y' replaced by W/V, output X/Y replaced by sqrt(r) Z5/Y5; plus common-subexpression elimination; plus assumption Z1=1. - Explicit formulas:
YY2 = Y2^

^{2}ZZ2 = r*Z2^^{2}A = ZZ2-YY2 B = ZZ2+YY2 YY3 = Y3^^{2}ZZ3 = r*Z3^^{2}V2 = s*A^^{2}W2 = B^^{2}Y4 = W2-V2 Z4 = W2+V2 V = s*A*(ZZ3-YY3) W = B*(ZZ3+YY3) Y5 = r*(W-V) Z5 = Y1*(W+V)

- Assumptions: s=(1+r)/(1-r).
- Cost: 4M + 6S + 3*r + 2*s + 8add.
- Source: 2006 Gaudry "Variants of the Montgomery form based on Theta functions", pages 22/52 and 23/52, with A^
^{2}/B^^{2}= (a^^{2}+b^^{2})/(a^^{2}-b^^{2}) as on page 20/52, replacing incorrect B^^{2}/A^^{2}and b/a on pages 22/52 and 23/52 with correct A^^{2}/B^^{2}and a/b; or 2009 Gaudry–Lubicz "The arithmetic of characteristic 2 Kummer surfaces and of elliptic Kummer lines", Section 6.2, replacing incorrect A'/B' = (a^^{2}+b^^{2})/(a^^{2}-b^^{2}) with correct A'^^{2}/B'^^{2}= (a^^{2}+b^^{2})/(a^^{2}-b^^{2}), replacing A'^^{2}/B'^^{2}with A^^{2}/B^^{2}, and replacing z... with y...; plus notation changes: a/b and A^^{2}/B^^{2}defined as 1/sqrt(r) and (1+r)/(1-r), input x^^{2}/y^^{2}etc. replaced by r Z2^^{2}/Y2^^{2}and r Z3^^{2}/Y3^^{2}and r Z1^^{2}/Y1^^{2}, intermediate x'/y' replaced by W/V, output X/Y replaced by sqrt(r) Z5/Y5; plus common-subexpression elimination. - Explicit formulas:
YY2 = Y2^

^{2}ZZ2 = r*Z2^^{2}A = ZZ2-YY2 B = ZZ2+YY2 YY3 = Y3^^{2}ZZ3 = r*Z3^^{2}V2 = s*A^^{2}W2 = B^^{2}Y4 = W2-V2 Z4 = W2+V2 V = s*A*(ZZ3-YY3) W = B*(ZZ3+YY3) Y5 = (r*Z1)*(W-V) Z5 = Y1*(W+V)

- Assumptions: s=(1+r)/(1-r).
- Cost: 4M + 14S + 7*r + 2*s + 10add.
- Source: 2006 Gaudry "Variants of the Montgomery form based on Theta functions", pages 22/52 and 23/52, with A^
^{2}/B^^{2}= (a^^{2}+b^^{2})/(a^^{2}-b^^{2}) as on page 20/52, replacing incorrect B^^{2}/A^^{2}and b/a on pages 22/52 and 23/52 with correct A^^{2}/B^^{2}and a/b; or 2009 Gaudry–Lubicz "The arithmetic of characteristic 2 Kummer surfaces and of elliptic Kummer lines", Section 6.2, replacing incorrect A'/B' = (a^^{2}+b^^{2})/(a^^{2}-b^^{2}) with correct A'^^{2}/B'^^{2}= (a^^{2}+b^^{2})/(a^^{2}-b^^{2}), replacing A'^^{2}/B'^^{2}with A^^{2}/B^^{2}, and replacing z... with y...; plus notation changes: a/b and A^^{2}/B^^{2}defined as 1/sqrt(r) and (1+r)/(1-r), input x^^{2}/y^^{2}etc. replaced by r Z2^^{2}/Y2^^{2}and r Z3^^{2}/Y3^^{2}and r Z1^^{2}/Y1^^{2}, intermediate x'/y' replaced by W/V, output X/Y replaced by sqrt(r) Z5/Y5. - Explicit formulas:
V2 = s*(r*Z2^

^{2}-Y2^^{2})^^{2}W2 = (r*Z2^^{2}+Y2^^{2})^^{2}Y4 = W2-V2 Z4 = W2+V2 V = s*(r*Z2^^{2}-Y2^^{2})*(r*Z3^^{2}-Y3^^{2}) W = (r*Z2^^{2}+Y2^^{2})*(r*Z3^^{2}+Y3^^{2}) Y5 = r*Z1*(W-V) Z5 = Y1*(W+V)

- Cost: 1I + 1M + 0add.
- Explicit formulas:
Y3 = Y1/Z1 Z3 = 1