Explicit-Formulas Database
Genus-1 curves over large-characteristic fields
Jacobi quartics EFD / Genus-1 large-characteristic / Doubling-oriented XXYZZR coordinates for Jacobi quartics

Doubling-oriented XXYZZR coordinates for Jacobi quartics

An elliptic curve in Jacobi quartic form [more information] has parameters a and coordinates x y satisfying the following equations:

  y^²=x^⁴+2*a*x^²+1

Doubling-oriented XXYZZR coordinates [database entry] make the additional assumptions

  a^²+c^²=1

and represent x y as X XX Y Z ZZ R satisfying the following equations:

  x=X/Z
  y=Y/ZZ
  XX=X^²
  ZZ=Z^²
  R=2*X*Z

Best operation counts

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

10M for addition: 7M+3S.
9M for addition with Z2=1: 6M+3S.
9M for addition with Z1=1 and Z2=1: 5M+4S. 6M+3S.
10M for readdition: 7M+3S after 7M+3S.
9M for readdition with Z2=1: 6M+3S after 6M+3S.
9M for readdition with Z1=1 and Z2=1: 5M+4S after 5M+4S. 6M+3S after 6M+3S.
7M for doubling: 2M+5S. 3M+4S.
7M for doubling with Z1=1: 1M+6S. 1M+6S. 2M+5S. 3M+4S.
15M for tripling: 4M+11S. 8M+7S.
103M for scaling: 1I+2M+1S.

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

9.4M for addition: 7M+3S.
8.4M for addition with Z2=1: 6M+3S.
8.2M for addition with Z1=1 and Z2=1: 5M+4S.
9.4M for readdition: 7M+3S after 7M+3S.
8.4M for readdition with Z2=1: 6M+3S after 6M+3S.
8.2M for readdition with Z1=1 and Z2=1: 5M+4S after 5M+4S.
6M for doubling: 2M+5S.
5.8M for doubling with Z1=1: 1M+6S. 1M+6S.
12.8M for tripling: 4M+11S.
102.8M for scaling: 1I+2M+1S.

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

9.01M for addition: 7M+3S.
8.01M for addition with Z2=1: 6M+3S.
7.68M for addition with Z1=1 and Z2=1: 5M+4S.
9.01M for readdition: 7M+3S after 7M+3S.
8.01M for readdition with Z2=1: 6M+3S after 6M+3S.
7.68M for readdition with Z1=1 and Z2=1: 5M+4S after 5M+4S.
5.35M for doubling: 2M+5S.
5.02M for doubling with Z1=1: 1M+6S. 1M+6S.
11.37M for tripling: 4M+11S.
102.67M for scaling: 1I+2M+1S.

Summary of all explicit formulas

Operation	Assumptions	Cost	Readdition cost
addition	Z1=1 and Z2=1	5M + 4S + 1*a	5M + 4S + 1*a
addition	Z2=1 and k=a-1	6M + 3S + 1*k	6M + 3S + 1*k
addition	Z2=1	7M + 3S + 1*a	7M + 3S + 1*a
addition	k=a-1	7M + 3S + 1*k	7M + 3S + 1*k
addition		8M + 3S + 1*a	8M + 3S + 1*a
addition	b=-2a and half2=1	9M + 2S + 2half + 1b	9M + 2S + 1half + 1b
doubling	Z1=1	1M + 6S + 1*a
doubling	Z1=1	1M + 6S
doubling		2M + 5S + 1*a
doubling		3M + 4S
doubling		8S + 1a + 2c
doubling		1M + 8S + 1*a
doubling	a2=2*a	3M + 9S + 2*a2
doubling		2M + 8S + 1^⁴ + 1a + 2c
tripling	b=a^²-1	4M + 11S + 1a + 1b
tripling		8M + 7S + 1*a
scaling		1I + 2M + 1S

Explicit formulas for addition

The "mmadd-2007-bl" addition formulas [database entry; Sage verification script; Sage output; three-operand code]:

Assumptions: Z1=1 and Z2=1.
Cost: 5M + 4S + 1*a + 12add + 1*2.
Cost: 5M + 4S + 1*a + 11add + 1*2 dependent upon the first point.
Source: 2007 Bernstein–Lange.
Strongly unified.

Explicit formulas:

      E1 = X1+Y1
      E2 = X2+Y2
      B = X1*X2
      XX1XX2 = B^²
      Y1Y2 = Y1*Y2
      F = 1+XX1XX2
      G = 2*B
      X3 = E1*E2-B-Y1Y2
      Y3 = F*(Y1Y2+a*G)+(XX1+XX2)*G
      Z3 = 1-XX1XX2
      XX3 = X3^²
      ZZ3 = Z3^²
      R3 = (X3+Z3)^²-XX3-ZZ3

The "madd-20080225-hwcd" addition formulas [database entry; Sage verification script; Sage output; three-operand code]:

Assumptions: Z2=1 and k=a-1.
Cost: 6M + 3S + 1*k + 15add + 3*2.
Cost: 6M + 3S + 1*k + 13add + 3*2 dependent upon the first point.
Source: 2008.02.25 Hisil–Wong–Carter–Dawson, plus U=XX, plus V=ZZ, plus W=R/2, plus rescaling, plus denominator elimination, plus standard streamlining, plus Z2=1.
Strongly unified.

Explicit formulas:

      A = 2*XX1*XX2
      B = 2*ZZ1
      C = R1*R2
      D = Y1*Y2
      X3 = (R1+Y1)*(R2+Y2)-C-D
      Z3 = B-A
      XX3 = X3^²
      ZZ3 = Z3^²
      F = A+B+C
      G = 2*((XX1+ZZ1)*(XX2+1)+D)+k*C
      H = XX3+ZZ3
      Y3 = F*G-H
      R3 = (X3+Z3)^²-H

The "madd-2007-bl" addition formulas [database entry; Sage verification script; Sage output; three-operand code]:

Assumptions: Z2=1.
Cost: 7M + 3S + 1*a + 14add + 2*2 + 1*4.
Cost: 7M + 3S + 1*a + 12add + 2*2 + 1*4 dependent upon the first point.
Source: 2007 Bernstein–Lange.
Strongly unified.

Explicit formulas:

      E1 = R1+Y1
      E2 = R2+Y2
      XX1XX2 = XX1*XX2
      R1R2 = R1*R2
      Y1Y2 = Y1*Y2
      F = ZZ1+XX1XX2
      G = 2*R1R2
      X3 = E1*E2-R1R2-Y1Y2
      Y3 = F*(4*Y1Y2+a*G)+((XX1+ZZ1)*(XX2+ZZ2)-F)*G
      Z3 = 2*(ZZ1-XX1XX2)
      XX3 = X3^²
      ZZ3 = Z3^²
      R3 = (X3+Z3)^²-XX3-ZZ3

The "add-20080225-hwcd" addition formulas [database entry; Sage verification script; Sage output; three-operand code]:

Assumptions: k=a-1.
Cost: 7M + 3S + 1*k + 15add + 3*2.
Cost: 7M + 3S + 1*k + 13add + 3*2 dependent upon the first point.
Source: 2008.02.25 Hisil–Wong–Carter–Dawson, plus U=XX, plus V=ZZ, plus W=R/2, plus rescaling, plus denominator elimination, plus standard streamlining.
Strongly unified.

Explicit formulas:

      A = 2*XX1*XX2
      B = 2*ZZ1*ZZ2
      C = R1*R2
      D = Y1*Y2
      X3 = (R1+Y1)*(R2+Y2)-C-D
      Z3 = B-A
      XX3 = X3^²
      ZZ3 = Z3^²
      F = A+B+C
      G = 2*((XX1+ZZ1)*(XX2+ZZ2)+D)+k*C
      H = XX3+ZZ3
      Y3 = F*G-H
      R3 = (X3+Z3)^²-H

The "add-2007-bl" addition formulas [database entry; Sage verification script; Sage output; three-operand code]:

Cost: 8M + 3S + 1*a + 14add + 2*2 + 1*4.
Cost: 8M + 3S + 1*a + 12add + 2*2 + 1*4 dependent upon the first point.
Source: 2007 Bernstein–Lange.
Strongly unified.

Explicit formulas:

      E1 = R1+Y1
      E2 = R2+Y2
      XX1XX2 = XX1*XX2
      R1R2 = R1*R2
      ZZ1ZZ2 = ZZ1*ZZ2
      Y1Y2 = Y1*Y2
      F = ZZ1ZZ2+XX1XX2
      G = 2*R1R2
      X3 = E1*E2-R1R2-Y1Y2
      Y3 = F*(4*Y1Y2+a*G)+((XX1+ZZ1)*(XX2+ZZ2)-F)*G
      Z3 = 2*(ZZ1ZZ2-XX1XX2)
      XX3 = X3^²
      ZZ3 = Z3^²
      R3 = (X3+Z3)^²-XX3-ZZ3

The "add-2007-d" addition formulas [database entry; Sage verification script; Sage output; three-operand code]:

Assumptions: b=-2*a and half*2=1.
Cost: 9M + 2S + 2*half + 1*b + 12add + 2*2.
Cost: 9M + 2S + 1*half + 1*b + 10add + 2*2 dependent upon the first point.
Source: 2007 Duquesne, page 103, Table 1, plus V=R/2.
Strongly unified.

Explicit formulas:

      A1 = XX1
      A2 = XX2
      A3 = half*R1
      A4 = half*R2
      A5 = ZZ1
      A6 = ZZ2
      A7 = Y1
      A8 = Y2
      A9 = A7*A8
      A7 = A7+A3
      A8 = A8+A4
      A3 = A3*A4
      A7 = A7*A8
      A7 = A7-A9
      A7 = A7-A3
      A4 = A1*A2
      A8 = A5*A6
      A1 = A1+A5
      A2 = A2+A6
      A5 = A1*A2
      A5 = A5-A4
      A5 = A5-A8
      A1 = A8-A4
      A2 = A8+A4
      A6 = b*A3
      A6 = A9-A6
      A6 = A6*A2
      A3 = 2*A3
      A3 = A5*A3
      A8 = A6+A3
      A2 = A7^²
      A4 = A1*A7
      A6 = A1^²
      X3 = A7
      Y3 = A8
      Z3 = A1
      XX3 = A2
      R3 = 2*A4
      ZZ3 = A6

Explicit formulas for doubling

The "mdbl-20090311-hwcd" doubling formulas [database entry; Sage verification script; Sage output; three-operand code]:

Assumptions: Z1=1.
Cost: 1M + 6S + 1*a + 6add + 1*2.
Source: 2009 Hisil–Wong–Carter–Dawson, formula (9), plus substitutions U = XX, V = ZZ, W = R/2, plus Z3 expansion using Z1=1.

Explicit formulas:

      YY1 = Y1^²
      X3 = Y1*R1
      Z3 = 1-XX1^²
      XX3 = X3^²
      ZZ3 = Z3^²
      R3 = (X3+Z3)^²-XX3-ZZ3
      Y3 = 2*YY1^²-a*XX3-ZZ3

The "mdbl-2007-hcd" doubling formulas [database entry; Sage verification script; Sage output; three-operand code]:

Assumptions: Z1=1.
Cost: 1M + 6S + 10add + 2*2.
Source: 2007 Hisil–Carter–Dawson.

Explicit formulas:

      A = XX1^²
      B = Y1^²
      X3 = XX1+B-(X1+Y1)^²
      Z3 = A-1
      XX3 = X3^²
      ZZ3 = Z3^²
      T3 = XX3+ZZ3
      R3 = (X3+Z3)^²-T3
      Y3 = 2*B*(A+2*XX1+1)-T3

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

Cost: 2M + 5S + 1*a + 7add + 1*2.
Source: 2009 Hisil–Wong–Carter–Dawson, formula (9), plus substitutions U = XX, V = ZZ, W = R/2.

Explicit formulas:

      YY1 = Y1^²
      X3 = Y1*R1
      Z3 = (ZZ1-XX1)*(ZZ1+XX1)
      XX3 = X3^²
      ZZ3 = Z3^²
      R3 = (X3+Z3)^²-XX3-ZZ3
      Y3 = 2*YY1^²-a*XX3-ZZ3

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

Cost: 3M + 4S + 8add + 1*2.
Source: 2007 Hisil–Carter–Dawson.

Explicit formulas:

      B = XX1-ZZ1
      T1 = XX1+ZZ1
      C = Y1*T1
      X3 = C-Y1*(T1+R1)
      Z3 = T1*B
      XX3 = X3^²
      ZZ3 = Z3^²
      T3 = XX3+ZZ3
      R3 = (X3+Z3)^²-T3
      Y3 = 2*C^²-T3

The "dbl-2007-fw-4" doubling formulas [database entry; Sage verification script; Sage output; three-operand code]:

Cost: 8S + 1*a + 2*c + 10add + 2*2 + 1*8.
Source: 2007 Feng–Wu, second JQN2 doubling formula, plus epsilon=1, plus delta=-a, plus scaling, plus common-subexpression elimination.

Explicit formulas:

      Y12 = 2*Y1
      T1 = R1^²
      T12 = 2*T1
      T2 = Y12^²
      X3 = (R1+Y12)^²-T1-T2
      XX3 = X3^²
      Y3 = (T2+c*T12)^²-c*XX3
      Z3 = T2-a*T12-8*XX1^²
      ZZ3 = Z3^²
      T3 = XX3+ZZ3
      R3 = (X3+Z3)^²-T3

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

Cost: 1M + 8S + 1*a + 10add + 2*2 + 1*4 + 1*8.
Source: 2007 Feng–Wu, first JQN2 doubling formula, plus correction of obvious typos, plus epsilon=1, plus delta=-a, plus scaling, plus common-subexpression elimination.

Explicit formulas:

      A1 = (R1+2*Y1)^²
      A2 = 4*Y1^²
      Q1 = XX1^²
      S1 = R1^²
      S12 = 2*S1
      M = a*S12
      A2M = A2-M
      X3 = A1-A2-S1
      Y3 = A2M*(A2+M)+S12^²
      Z3 = A2M-8*Q1
      XX3 = X3^²
      ZZ3 = Z3^²
      T3 = XX3+ZZ3
      R3 = (X3+Z3)^²-T3

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

Assumptions: a2=2*a.
Cost: 3M + 9S + 2*a2 + 12add + 1*4.
Source: 2007 Feng–Wu, first JQN2 doubling formula, plus correction of obvious typos, plus epsilon=1, plus delta=-a.

Explicit formulas:

      A1 = (X1*Z1+Y1)^²
      A2 = Y1^²
      Q1 = (X1^²)^²
      S1 = (X1*Z1)^²
      T = A2-Q1-a2*S1
      X3 = A1-A2-S1
      Y3 = (T+Q1)*(A2+a2*S1)+4*S1^²
      Z3 = T-Q1
      XX3 = X3^²
      ZZ3 = Z3^²
      T3 = XX3+ZZ3
      R3 = (X3+Z3)^²-T3

The "dbl-2007-fw-3" doubling formulas [database entry; Sage verification script; Sage output; three-operand code]:

Cost: 2M + 8S + 1^⁴ + 1*a + 2*c + 10add + 3*2.
Source: 2007 Feng–Wu, second JQN2 doubling formula, plus epsilon=1, plus delta=-a.

Explicit formulas:

      T1 = (X1*Z1)^²
      T2 = Y1^²
      S1 = (T2+2*c*T1)^²
      U = (X1*Z1+Y1)^²-T1-T2
      Q = U^²
      X3 = U
      Y3 = S1-c*Q
      Z3 = T2-2*a*T1-2*X1^⁴
      XX3 = X3^²
      ZZ3 = Z3^²
      T3 = XX3+ZZ3
      R3 = (X3+Z3)^²-T3

Explicit formulas for tripling

The "tpl-2007-hcd-2" tripling formulas [database entry; Sage verification script; Sage output; three-operand code]:

Assumptions: b=a^²-1.
Cost: 4M + 11S + 1*a + 1*b + 13add + 2*2 + 2*4.
Source: 2007 Hisil–Carter–Dawson.

Explicit formulas:

      UU = XX1^²
      WW = ZZ1^²
      RR = R1^²
      A = 4*(UU-WW)
      AA = A^²
      B = 2*(UU+WW)+a*RR
      BB = B^²
      AB = (A+B)^²-AA-BB
      C = b*RR^²
      Q = 2*(BB-C)
      X3 = X1*(AB-Q)
      Z3 = Z1*(AB+Q)
      Y3 = Y1*(Q^²-4*AA*C)
      XX3 = X3^²
      ZZ3 = Z3^²
      R3 = (X3+Z3)^²-XX3-ZZ3

The "tpl-2007-hcd" tripling formulas [database entry; Sage verification script; Sage output; three-operand code]:

Cost: 8M + 7S + 1*a + 15add + 4*2.
Source: 2007 Hisil–Carter–Dawson.

Explicit formulas:

      A = XX1^²
      B = ZZ1^²
      C = A+B
      D = 2*((XX1+ZZ1)^²-C)
      E = A-B
      F = 2*A
      G = 2*B
      J = a*D+2*C
      K = J+E
      L = J-E
      M = C*E
      N = G*K
      P = F*L
      X3 = X1*(M-N)
      Y3 = Y1*((M+N)*(P-M)+(D*E)^²)
      Z3 = Z1*(P+M)
      XX3 = X3^²
      ZZ3 = Z3^²
      R3 = (X3+Z3)^²-XX3-ZZ3

Explicit formulas for differential addition

Explicit formulas for differential addition and doubling

Explicit formulas for scaling

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

Cost: 1I + 2M + 1S + 0add + 3*2.

Explicit formulas:

      A = 2*ZZ1
      B = 1/A
      X3 = R1*B
      Y3 = 2*Y1*B
      XX3 = X3^²
      R3 = 2*X3
      Z3 = 1
      ZZ3 = 1