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

Doubling-oriented XXYZZ 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 XXYZZ coordinates [database entry] make the additional assumptions

  a^²+c^²=1

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

  x=X/Z
  y=Y/ZZ
  XX=X^²
  ZZ=Z^²

Best operation counts

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

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

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

10.2M for addition: 7M+4S.
8.4M for addition with Z2=1: 6M+3S.
9.4M for readdition: 7M+3S after 7M+4S.
8.4M for readdition with Z2=1: 6M+3S after 6M+3S.
6M for doubling: 2M+5S.
4.8M for doubling with Z1=1: 6S.
12.8M for tripling: 4M+11S. 8M+6S.
103.6M for scaling: 1I+2M+2S.

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

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

Summary of all explicit formulas

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

Explicit formulas for addition

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 + 16add + 4*2.
Cost: 6M + 3S + 1*k + 14add + 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:

      R1 = (X1+Z1)^²-XX1-ZZ1
      R2 = 2*X2
      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

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

Assumptions: k=a-1.
Cost: 7M + 4S + 1*k + 19add + 3*2.
Cost: 7M + 3S + 1*k + 14add + 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:

      R1 = (X1+Z1)^²-XX1-ZZ1
      R2 = (X2+Z2)^²-XX2-ZZ2
      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

Explicit formulas for doubling

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

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

Explicit formulas:

      YY1 = Y1^²
      X3 = (X1+Y1)^²-XX1-YY1
      Z3 = 1-XX1^²
      XX3 = X3^²
      ZZ3 = Z3^²
      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 + 5S + 8add + 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
      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, plus R rotation.

Explicit formulas:

      R1 = (X1+Z1)^²-XX1-ZZ1
      YY1 = Y1^²
      X3 = Y1*R1
      Z3 = (ZZ1-XX1)*(ZZ1+XX1)
      XX3 = X3^²
      ZZ3 = Z3^²
      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 + 6add + 1*2.
Source: 2007 Hisil–Carter–Dawson.

Explicit formulas:

      B = XX1-ZZ1
      T1 = XX1+ZZ1
      C = Y1*T1
      X3 = C-Y1*(X1+Z1)^²
      Z3 = T1*B
      XX3 = X3^²
      ZZ3 = Z3^²
      T3 = XX3+ZZ3
      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:

      R1 = (X1+Z1)^²-XX1-ZZ1
      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^²

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:

      R1 = (X1+Z1)^²-XX1-ZZ1
      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^²

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

Assumptions: a2=2*a.
Cost: 3M + 8S + 1*a2 + 1*a + 10add + 1*2 + 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-2*a*S1
      X3 = A1-A2-S1
      Y3 = (T+Q1)*(A2+a2*S1)+4*S1^²
      Z3 = T-Q1
      XX3 = X3^²
      ZZ3 = Z3^²
      T3 = XX3+ZZ3

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

Assumptions: a2=2*a.
Cost: 2M + 7S + 1^⁴ + 1*a2 + 2*c + 7add + 2*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-a2*T1-2*X1^⁴
      XX3 = X3^²
      ZZ3 = Z3^²

Explicit formulas for tripling

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

Cost: 8M + 6S + 1*a + 12add + 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^²

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 = ((X1+Z1)^²-XX1-ZZ1)^²
      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^²

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 + 2S + 0add.

Explicit formulas:

      A = 1/Z1
      X3 = X1*A
      XX3 = X3^²
      Y3 = Y1*A^²
      Z3 = 1
      ZZ3 = 1