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

# Squared 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^2+y^2=c^2*(1+d*x^2*y^2)
```

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

```  c=1
d=r^2
```
and represent x y as Y Z satisfying the following equations:
```  r*y^2=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.
• 3M for doubling with Z1=1: 3S.
• 6M for differential addition: 4M+2S.
• 5M for differential addition with Z1=1: 3M+2S.
• 10M for differential addition and doubling: 4M+6S. 4M+6S.
• 9M for differential addition and doubling with Z1=1: 3M+6S. 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.
• 2.4M for doubling with Z1=1: 3S.
• 5.6M for differential addition: 4M+2S.
• 4.6M for differential addition with Z1=1: 3M+2S.
• 8.8M for differential addition and doubling: 4M+6S. 4M+6S.
• 7.8M for differential addition and doubling with Z1=1: 3M+6S. 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.
• 2.01M for doubling with Z1=1: 3S.
• 5.34M for differential addition: 4M+2S.
• 4.34M for differential addition with Z1=1: 3M+2S.
• 8.02M for differential addition and doubling: 4M+6S. 4M+6S.
• 7.02M for differential addition and doubling with Z1=1: 3M+6S. 3M+6S.
• 101M for scaling: 1I+1M.

## Summary of all explicit formulas

doubling Z1=1 and s=(1+r)/(1-r) 3S + 1*r + 1*s
doubling s=(1+r)/(1-r) 4S + 1*r + 1*s
diffadd Z1=1 and s=(1+r)/(1-r) 3M + 2S + 1*s
diffadd s=(1+r)/(1-r) 4M + 2S + 1*s
ladder Z1=1 and s=(1+r)/(1-r) 3M + 6S + 1*r + 2*s
ladder Z1=1 and s=(1+r)/(1-r) 3M + 6S + 1*r + 2*s
ladder s=(1+r)/(1-r) 4M + 6S + 1*r + 2*s
ladder s=(1+r)/(1-r) 4M + 6S + 1*r + 2*s
scaling 1I + 1M

## Explicit formulas for doubling

The "mdbl-2006-g" doubling formulas [database entry; Sage verification script; Sage output; three-operand code]:
• Assumptions: Z1=1 and s=(1+r)/(1-r).
• Cost: 3S + 1*r + 1*s + 4add + 1*4.
• Source: 2006 Gaudry "Variants of the Montgomery form based on Theta functions", page 22/52, with A2/B2 = (a2+b2)/(a2-b2) as on page 20/52, replacing incorrect B2/A2 and b/a on page 22/52 with correct A2/B2 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' = (a2+b2)/(a2-b2) with correct A'2/B'2 = (a2+b2)/(a2-b2), replacing A'2/B'2 with A2/B2, and replacing z... with y...; plus notation changes: a/b and A2/B2 defined as 1/sqrt(r) and (1+r)/(1-r), input x2/y2 replaced by Z1/Y1, intermediate x'/y' replaced by W/V, output X2/Y2 replaced by Z3/Y3; plus assumption Z1=1; plus standard simplification.
• Explicit formulas:
```      W = (1+Y1)^2
V = s*(W-4*Y1)
Y3 = (W-V)^2
Z3 = r*(W+V)^2
```

The "dbl-2006-g" 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 A2/B2 = (a2+b2)/(a2-b2) as on page 20/52, replacing incorrect B2/A2 and b/a on page 22/52 with correct A2/B2 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' = (a2+b2)/(a2-b2) with correct A'2/B'2 = (a2+b2)/(a2-b2), replacing A'2/B'2 with A2/B2, and replacing z... with y...; plus notation changes: a/b and A2/B2 defined as 1/sqrt(r) and (1+r)/(1-r), input x2/y2 replaced by Z1/Y1, intermediate x'/y' replaced by W/V, output X2/Y2 replaced by Z3/Y3.
• Explicit formulas:
```      V = s*(Z1-Y1)^2
W = (Z1+Y1)^2
Y3 = (W-V)^2
Z3 = r*(W+V)^2
```

## Explicit formulas for differential addition

The "mdadd-2006-g" differential-addition formulas [database entry; Sage verification script; Sage output; three-operand code]:
• Assumptions: Z1=1 and s=(1+r)/(1-r).
• Cost: 3M + 2S + 1*s + 6add.
• Source: 2006 Gaudry "Variants of the Montgomery form based on Theta functions", page 23/52, with A2/B2 = (a2+b2)/(a2-b2) as on page 20/52, replacing incorrect B2/A2 on page 23/52 with correct A2/B2 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' = (a2+b2)/(a2-b2) with correct A'2/B'2 = (a2+b2)/(a2-b2), replacing A'2/B'2 with A2/B2, and replacing z... with y...; plus notation changes: a/b and A2/B2 defined as 1/sqrt(r) and (1+r)/(1-r), input x2/y2 etc. replaced by Z2/Y2 and Z3/Y3 and Z1/Y1, intermediate x'/y' replaced by W/V, output X2/Y2 replaced by Z5/Y5; plus assumption Z1=1.
• Explicit formulas:
```      V = s*(Z2-Y2)*(Z3-Y3)
W = (Z2+Y2)*(Z3+Y3)
Y5 = (W-V)^2
Z5 = Y1*(W+V)^2
```

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 + 2S + 1*s + 6add.
• Source: 2006 Gaudry "Variants of the Montgomery form based on Theta functions", page 23/52, with A2/B2 = (a2+b2)/(a2-b2) as on page 20/52, replacing incorrect B2/A2 on page 23/52 with correct A2/B2 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' = (a2+b2)/(a2-b2) with correct A'2/B'2 = (a2+b2)/(a2-b2), replacing A'2/B'2 with A2/B2, and replacing z... with y...; plus notation changes: a/b and A2/B2 defined as 1/sqrt(r) and (1+r)/(1-r), input x2/y2 etc. replaced by Z2/Y2 and Z3/Y3 and Z1/Y1, intermediate x'/y' replaced by W/V, output X2/Y2 replaced by Z5/Y5.
• Explicit formulas:
```      V = s*(Z2-Y2)*(Z3-Y3)
W = (Z2+Y2)*(Z3+Y3)
Y5 = Z1*(W-V)^2
Z5 = Y1*(W+V)^2
```

## 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: Z1=1 and s=(1+r)/(1-r).
• Cost: 3M + 6S + 1*r + 2*s + 8add.
• Source: 2006 Gaudry "Variants of the Montgomery form based on Theta functions", pages 22/52 and 23/52, with A2/B2 = (a2+b2)/(a2-b2) as on page 20/52, replacing incorrect B2/A2 on pages 22/52 and 23/52 with correct A2/B2 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' = (a2+b2)/(a2-b2) with correct A'2/B'2 = (a2+b2)/(a2-b2), replacing A'2/B'2 with A2/B2, and replacing z... with y...; plus notation changes: a/b and A2/B2 defined as 1/sqrt(r) and (1+r)/(1-r), input x2/y2 etc. replaced by Z2/Y2 and Z3/Y3 and Z1/Y1, intermediate x'/y' replaced by W/V, output X2/Y2 replaced by Z5/Y5; plus common-subexpression elimination; plus assumption Z1=1.
• Explicit formulas:
```      A = Z2-Y2
B = Z2+Y2
V2 = s*A^2
W2 = B^2
Y4 = (W2-V2)^2
Z4 = r*(W2+V2)^2
V = s*A*(Z3-Y3)
W = B*(Z3+Y3)
Y5 = (W-V)^2
Z5 = Y1*(W+V)^2
```

The "mladd-2006-g" differential-addition-and-doubling formulas [database entry; Sage verification script; Sage output; three-operand code]:
• Assumptions: Z1=1 and s=(1+r)/(1-r).
• Cost: 3M + 6S + 1*r + 2*s + 10add.
• Source: 2006 Gaudry "Variants of the Montgomery form based on Theta functions", pages 22/52 and 23/52, with A2/B2 = (a2+b2)/(a2-b2) as on page 20/52, replacing incorrect B2/A2 on pages 22/52 and 23/52 with correct A2/B2 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' = (a2+b2)/(a2-b2) with correct A'2/B'2 = (a2+b2)/(a2-b2), replacing A'2/B'2 with A2/B2, and replacing z... with y...; plus notation changes: a/b and A2/B2 defined as 1/sqrt(r) and (1+r)/(1-r), input x2/y2 etc. replaced by Z2/Y2 and Z3/Y3 and Z1/Y1, intermediate x'/y' replaced by W/V, output X2/Y2 replaced by Z5/Y5; plus assumption Z1=1.
• Explicit formulas:
```      V2 = s*(Z2-Y2)^2
W2 = (Z2+Y2)^2
Y4 = (W2-V2)^2
Z4 = r*(W2+V2)^2
V = s*(Z2-Y2)*(Z3-Y3)
W = (Z2+Y2)*(Z3+Y3)
Y5 = (W-V)^2
Z5 = Y1*(W+V)^2
```

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 + 1*r + 2*s + 8add.
• Source: 2006 Gaudry "Variants of the Montgomery form based on Theta functions", pages 22/52 and 23/52, with A2/B2 = (a2+b2)/(a2-b2) as on page 20/52, replacing incorrect B2/A2 on pages 22/52 and 23/52 with correct A2/B2 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' = (a2+b2)/(a2-b2) with correct A'2/B'2 = (a2+b2)/(a2-b2), replacing A'2/B'2 with A2/B2, and replacing z... with y...; plus notation changes: a/b and A2/B2 defined as 1/sqrt(r) and (1+r)/(1-r), input x2/y2 etc. replaced by Z2/Y2 and Z3/Y3 and Z1/Y1, intermediate x'/y' replaced by W/V, output X2/Y2 replaced by Z5/Y5; plus common-subexpression elimination.
• Explicit formulas:
```      A = Z2-Y2
B = Z2+Y2
V2 = s*A^2
W2 = B^2
Y4 = (W2-V2)^2
Z4 = r*(W2+V2)^2
V = s*A*(Z3-Y3)
W = B*(Z3+Y3)
Y5 = Z1*(W-V)^2
Z5 = Y1*(W+V)^2
```

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 + 6S + 1*r + 2*s + 10add.
• Source: 2006 Gaudry "Variants of the Montgomery form based on Theta functions", pages 22/52 and 23/52, with A2/B2 = (a2+b2)/(a2-b2) as on page 20/52, replacing incorrect B2/A2 on pages 22/52 and 23/52 with correct A2/B2 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' = (a2+b2)/(a2-b2) with correct A'2/B'2 = (a2+b2)/(a2-b2), replacing A'2/B'2 with A2/B2, and replacing z... with y...; plus notation changes: a/b and A2/B2 defined as 1/sqrt(r) and (1+r)/(1-r), input x2/y2 etc. replaced by Z2/Y2 and Z3/Y3 and Z1/Y1, intermediate x'/y' replaced by W/V, output X2/Y2 replaced by Z5/Y5.
• Explicit formulas:
```      V2 = s*(Z2-Y2)^2
W2 = (Z2+Y2)^2
Y4 = (W2-V2)^2
Z4 = r*(W2+V2)^2
V = s*(Z2-Y2)*(Z3-Y3)
W = (Z2+Y2)*(Z3+Y3)
Y5 = Z1*(W-V)^2
Z5 = Y1*(W+V)^2
```

## 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
```