Explicit-Formulas Database
Genus-1 curves over large-characteristic fields
Edwards curves EFD / Genus-1 large-characteristic / YZ coordinates with square d for Edwards curves

YZ coordinates with square d for Edwards curves

An elliptic curve in Edwards form [more information] has parameters c d and coordinates x y satisfying the following equations:

  x^²+y^²=c^²*(1+d*x^²*y^²)

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:

  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.

Best operation counts

Smallest multiplication counts assuming I=100M, S=1M, *param=0M, add=0M, *const=0M:

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.

Smallest multiplication counts assuming I=100M, S=0.8M, *param=0M, add=0M, *const=0M:

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.

Smallest multiplication counts assuming I=100M, S=0.67M, *param=0M, add=0M, *const=0M:

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.

Summary of all explicit formulas

Operation	Assumptions	Cost
doubling	s=(1+r)/(1-r) and r2=2*r and Z1=1	2S + 1r2 + 1s
doubling	s=(1+r)/(1-r) and Z1=1	3S + 1*s
doubling	s=(1+r)/(1-r)	4S + 1r + 1s
doubling	s=(1+r)/(1-r)	6S + 2r + 1s
diffadd	s=(1+r)/(1-r) and Z1=1	3M + 4S + 3r + 1s
diffadd	s=(1+r)/(1-r)	4M + 4S + 3r + 1s
diffadd	s=(1+r)/(1-r)	4M + 8S + 5r + 1s
ladder	s=(1+r)/(1-r) and Z1=1	3M + 6S + 3r + 2s
ladder	s=(1+r)/(1-r)	4M + 6S + 3r + 2s
ladder	s=(1+r)/(1-r)	4M + 14S + 7r + 2s
scaling		1I + 1M

Explicit formulas for addition

Explicit formulas for doubling

The "mdbl-2006-g-2" doubling formulas [database entry; Sage verification script; Sage output; three-operand code]:

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^²/B^² = (a^²+b^²)/(a^²-b^²) as on page 20/52, replacing incorrect B^²/A^² and b/a on page 22/52 with correct A^²/B^² 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^²+b^²)/(a^²-b^²) with correct A'^²/B'^² = (a^²+b^²)/(a^²-b^²), replacing A'^²/B'^² with A^²/B^², and replacing z... with y...; plus notation changes: a/b and A^²/B^² defined as 1/sqrt(r) and (1+r)/(1-r), input x^²/y^² replaced by r Z1^²/Y1^², 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^²
      A = r2*YY
      B = d+YY^²
      V = s*(B-A)
      W = B+A
      Y3 = W-V
      Z3 = W+V

The "mdbl-2006-g-3" doubling formulas [database entry; Sage verification script; Sage output; three-operand code]:

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^²/B^² = (a^²+b^²)/(a^²-b^²) as on page 20/52, replacing incorrect B^²/A^² and b/a on page 22/52 with correct A^²/B^² 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^²+b^²)/(a^²-b^²) with correct A'^²/B'^² = (a^²+b^²)/(a^²-b^²), replacing A'^²/B'^² with A^²/B^², and replacing z... with y...; plus notation changes: a/b and A^²/B^² defined as 1/sqrt(r) and (1+r)/(1-r), input x^²/y^² replaced by r Z1^²/Y1^², 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^²
      B = d+YY^²
      W = (r+YY)^²
      V = s*(2*B-W)
      Y3 = W-V
      Z3 = W+V

The "dbl-2006-g-2" doubling formulas [database entry; Sage verification script; Sage output; three-operand code]:

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^²/B^² = (a^²+b^²)/(a^²-b^²) as on page 20/52, replacing incorrect B^²/A^² and b/a on page 22/52 with correct A^²/B^² 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^²+b^²)/(a^²-b^²) with correct A'^²/B'^² = (a^²+b^²)/(a^²-b^²), replacing A'^²/B'^² with A^²/B^², and replacing z... with y...; plus notation changes: a/b and A^²/B^² defined as 1/sqrt(r) and (1+r)/(1-r), input x^²/y^² replaced by r Z1^²/Y1^², intermediate x'/y' replaced by W/V, output X/Y replaced by sqrt(r) Z3/Y3; plus common-subexpression elimination.

Explicit formulas:

      YY = Y1^²
      ZZ = r*Z1^²
      V = s*(ZZ-YY)^²
      W = (ZZ+YY)^²
      Y3 = W-V
      Z3 = W+V

The "dbl-2006-g" doubling formulas [database entry; Sage verification script; Sage output; three-operand code]:

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^²/B^² = (a^²+b^²)/(a^²-b^²) as on page 20/52, replacing incorrect B^²/A^² and b/a on page 22/52 with correct A^²/B^² 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^²+b^²)/(a^²-b^²) with correct A'^²/B'^² = (a^²+b^²)/(a^²-b^²), replacing A'^²/B'^² with A^²/B^², and replacing z... with y...; plus notation changes: a/b and A^²/B^² defined as 1/sqrt(r) and (1+r)/(1-r), input x^²/y^² replaced by r Z1^²/Y1^², intermediate x'/y' replaced by W/V, output X/Y replaced by sqrt(r) Z3/Y3.

Explicit formulas:

      V = s*(r*Z1^²-Y1^²)^²
      W = (r*Z1^²+Y1^²)^²
      Y3 = W-V
      Z3 = W+V

Explicit formulas for tripling

Explicit formulas for differential addition

The "mdadd-2006-g-2" differential-addition formulas [database entry; Sage verification script; Sage output; three-operand code]:

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^²/B^² = (a^²+b^²)/(a^²-b^²) as on page 20/52, replacing incorrect B^²/A^² on page 23/52 with correct A^²/B^² 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^²+b^²)/(a^²-b^²) with correct A'^²/B'^² = (a^²+b^²)/(a^²-b^²), replacing A'^²/B'^² with A^²/B^², and replacing z... with y...; plus notation changes: a/b and A^²/B^² defined as 1/sqrt(r) and (1+r)/(1-r), input x^²/y^² etc. replaced by r Z2^²/Y2^² and r Z3^²/Y3^² and r Z1^²/Y1^², 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^²
      ZZ2 = r*Z2^²
      YY3 = Y3^²
      ZZ3 = r*Z3^²
      V = s*(ZZ2-YY2)*(ZZ3-YY3)
      W = (ZZ2+YY2)*(ZZ3+YY3)
      Y5 = r*(W-V)
      Z5 = Y1*(W+V)

The "dadd-2006-g-2" differential-addition formulas [database entry; Sage verification script; Sage output; three-operand code]:

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^²/B^² = (a^²+b^²)/(a^²-b^²) as on page 20/52, replacing incorrect B^²/A^² on page 23/52 with correct A^²/B^² 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^²+b^²)/(a^²-b^²) with correct A'^²/B'^² = (a^²+b^²)/(a^²-b^²), replacing A'^²/B'^² with A^²/B^², and replacing z... with y...; plus notation changes: a/b and A^²/B^² defined as 1/sqrt(r) and (1+r)/(1-r), input x^²/y^² etc. replaced by r Z2^²/Y2^² and r Z3^²/Y3^² and r Z1^²/Y1^², intermediate x'/y' replaced by W/V, output X/Y replaced by sqrt(r) Z5/Y5; plus common-subexpression elimination.

Explicit formulas:

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

The "dadd-2006-g" differential-addition formulas [database entry; Sage verification script; Sage output; three-operand code]:

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^²/B^² = (a^²+b^²)/(a^²-b^²) as on page 20/52, replacing incorrect B^²/A^² on page 23/52 with correct A^²/B^² 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^²+b^²)/(a^²-b^²) with correct A'^²/B'^² = (a^²+b^²)/(a^²-b^²), replacing A'^²/B'^² with A^²/B^², and replacing z... with y...; plus notation changes: a/b and A^²/B^² defined as 1/sqrt(r) and (1+r)/(1-r), input x^²/y^² etc. replaced by r Z2^²/Y2^² and r Z3^²/Y3^² and r Z1^²/Y1^², intermediate x'/y' replaced by W/V, output X/Y replaced by sqrt(r) Z5/Y5.

Explicit formulas:

      V = s*(r*Z2^²-Y2^²)*(r*Z3^²-Y3^²)
      W = (r*Z2^²+Y2^²)*(r*Z3^²+Y3^²)
      Y5 = r*Z1*(W-V)
      Z5 = Y1*(W+V)

Explicit formulas for differential addition and doubling

The "mladd-2006-g-2" differential-addition-and-doubling formulas [database entry; Sage verification script; Sage output; three-operand code]:

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^²/B^² = (a^²+b^²)/(a^²-b^²) as on page 20/52, replacing incorrect B^²/A^² and b/a on pages 22/52 and 23/52 with correct A^²/B^² 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^²+b^²)/(a^²-b^²) with correct A'^²/B'^² = (a^²+b^²)/(a^²-b^²), replacing A'^²/B'^² with A^²/B^², and replacing z... with y...; plus notation changes: a/b and A^²/B^² defined as 1/sqrt(r) and (1+r)/(1-r), input x^²/y^² etc. replaced by r Z2^²/Y2^² and r Z3^²/Y3^² and r Z1^²/Y1^², 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^²
      ZZ2 = r*Z2^²
      A = ZZ2-YY2
      B = ZZ2+YY2
      YY3 = Y3^²
      ZZ3 = r*Z3^²
      V2 = s*A^²
      W2 = B^²
      Y4 = W2-V2
      Z4 = W2+V2
      V = s*A*(ZZ3-YY3)
      W = B*(ZZ3+YY3)
      Y5 = r*(W-V)
      Z5 = Y1*(W+V)

The "ladd-2006-g-2" differential-addition-and-doubling formulas [database entry; Sage verification script; Sage output; three-operand code]:

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^²/B^² = (a^²+b^²)/(a^²-b^²) as on page 20/52, replacing incorrect B^²/A^² and b/a on pages 22/52 and 23/52 with correct A^²/B^² 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^²+b^²)/(a^²-b^²) with correct A'^²/B'^² = (a^²+b^²)/(a^²-b^²), replacing A'^²/B'^² with A^²/B^², and replacing z... with y...; plus notation changes: a/b and A^²/B^² defined as 1/sqrt(r) and (1+r)/(1-r), input x^²/y^² etc. replaced by r Z2^²/Y2^² and r Z3^²/Y3^² and r Z1^²/Y1^², intermediate x'/y' replaced by W/V, output X/Y replaced by sqrt(r) Z5/Y5; plus common-subexpression elimination.

Explicit formulas:

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

The "ladd-2006-g" differential-addition-and-doubling formulas [database entry; Sage verification script; Sage output; three-operand code]:

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^²/B^² = (a^²+b^²)/(a^²-b^²) as on page 20/52, replacing incorrect B^²/A^² and b/a on pages 22/52 and 23/52 with correct A^²/B^² 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^²+b^²)/(a^²-b^²) with correct A'^²/B'^² = (a^²+b^²)/(a^²-b^²), replacing A'^²/B'^² with A^²/B^², and replacing z... with y...; plus notation changes: a/b and A^²/B^² defined as 1/sqrt(r) and (1+r)/(1-r), input x^²/y^² etc. replaced by r Z2^²/Y2^² and r Z3^²/Y3^² and r Z1^²/Y1^², intermediate x'/y' replaced by W/V, output X/Y replaced by sqrt(r) Z5/Y5.

Explicit formulas:

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

Explicit formulas for scaling

The "scale" scaling formulas [database entry; Sage verification script; Sage output; three-operand code]:

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