Explicit-Formulas Database
Genus-1 curves over large-characteristic fields
Jacobi intersections EFD / Genus-1 large-characteristic / Extended coordinates for Jacobi intersections

Extended coordinates for Jacobi intersections

An elliptic curve in Jacobi intersection form [more information] has parameters a and coordinates s c d satisfying the following equations:

  s^²+c^²=1
  a*s^²+d^²=1

Extended coordinates [database entry] represent s c d as S C D Z SC DZ satisfying the following equations:

  s=S/Z
  c=C/Z
  d=D/Z
  SC=S*C
  DZ=D*Z

Best operation counts

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

12M for addition: 11M+1S.
12M for addition with S2=1: 11M+1S.
11M for addition with Z2=1: 10M+1S.
11M for addition with Z1=1 and Z2=1: 10M+1S.
12M for readdition: 11M+1S after 11M+1S.
12M for readdition with S2=1: 11M+1S after 11M+1S.
11M for readdition with Z2=1: 10M+1S after 10M+1S.
11M for readdition with Z1=1 and Z2=1: 10M+1S after 10M+1S. 10M+1S after 10M+2S.
7M for doubling: 2M+5S.
7M for doubling with Z1=1: 2M+5S.
16M for tripling: 6M+10S. 6M+10S. 9M+7S. 9M+7S.
104M for scaling: 1I+4M.

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

11.8M for addition: 11M+1S.
11.8M for addition with S2=1: 11M+1S.
10.8M for addition with Z2=1: 10M+1S.
10.8M for addition with Z1=1 and Z2=1: 10M+1S.
11.8M for readdition: 11M+1S after 11M+1S.
11.8M for readdition with S2=1: 11M+1S after 11M+1S.
10.8M for readdition with Z2=1: 10M+1S after 10M+1S.
10.8M for readdition with Z1=1 and Z2=1: 10M+1S after 10M+1S. 10M+1S after 10M+2S.
6M for doubling: 2M+5S.
6M for doubling with Z1=1: 2M+5S.
14M for tripling: 6M+10S. 6M+10S.
104M for scaling: 1I+4M.

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

11.67M for addition: 11M+1S.
11.67M for addition with S2=1: 11M+1S.
10.67M for addition with Z2=1: 10M+1S.
10.67M for addition with Z1=1 and Z2=1: 10M+1S.
11.67M for readdition: 11M+1S after 11M+1S.
11.67M for readdition with S2=1: 11M+1S after 11M+1S.
10.67M for readdition with Z2=1: 10M+1S after 10M+1S.
10.67M for readdition with Z1=1 and Z2=1: 10M+1S after 10M+1S. 10M+1S after 10M+2S.
5.35M for doubling: 2M+5S.
5.35M for doubling with Z1=1: 2M+5S.
12.7M for tripling: 6M+10S. 6M+10S.
104M for scaling: 1I+4M.

Summary of all explicit formulas

Operation	Assumptions	Cost	Readdition cost
addition	Z2=1	10M + 1S + 2*a	10M + 1S + 2*a
addition	Z1=1 and Z2=1	10M + 2S + 1*a	10M + 1S + 1*a
addition		11M + 1S + 2*a	11M + 1S + 2*a
addition	Z2=1	13M + 2S + 1*a	12M + 2S + 1*a
addition	S2=1	13M + 2S + 1*a	12M + 2S + 1*a
addition		15M + 2S + 1*a	13M + 2S + 1*a
addition		16M + 2S + 1*a	14M + 2S + 1*a
addition		22M + 2S + 1*a	20M + 2S + 1*a
doubling		2M + 5S + 1*a
doubling	Z1=1	4M + 4S
doubling		5M + 4S
doubling		6M + 3S
doubling		7M + 3S
doubling		14M + 9S
tripling	b=a-1 and b2=2b and b3=3b and bb2=2bb	6M + 10S + 1bb2 + 1b2 + 2a + 1b3
tripling	b=a-1 and b2=2b and bb2=2bb and b3=3b	6M + 10S + 1bb2 + 1b2 + 2a + 1b3
tripling	b=a-1	9M + 7S + 3*b
tripling	b=a-1	9M + 7S + 5*b
scaling		1I + 4M

Explicit formulas for addition

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

Assumptions: Z2=1.
Cost: 10M + 1S + 2*a + 14add + 1*2.
Cost: 10M + 1S + 2*a + 13add + 1*2 dependent upon the first point.
Source: 2008.02.25 Hisil–Wong–Carter–Dawson, page 6.
Strongly unified.

Explicit formulas:

      E = S1*D2
      G = D1*S2
      H = Z1*C2
      J = SC1*D2
      K = DZ1*SC2
      S3 = (H+C1)*(E+G)-J-K
      C3 = (H+E)*(C1-G)-J+K
      D3 = (DZ1-a*SC1)*(SC2+D2)+a*J-K
      Z3 = (H+G)^²-2*K
      SC3 = S3*C3
      DZ3 = D3*Z3

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

Assumptions: Z1=1 and Z2=1.
Cost: 10M + 2S + 1*a + 7add.
Cost: 10M + 1S + 1*a + 7add dependent upon the first point.
Source: 2001 Liardet–Smart "Preventing SPA/DPA in ECC systems using the Jacobi form", plus Z1=1, plus Z2=1.
Strongly unified.

Explicit formulas:

      S1D2 = S1*D2
      D1S2 = D1*S2
      U = C2*C1
      V = D1S2*S1D2
      S3 = (C2+D1S2)*(C1+S1D2)-U-V
      C3 = U-V
      D3 = D1*D2-a*S1*S2*U
      Z3 = C2^²+D1S2^²
      SC3 = S3*C3
      DZ3 = D3*Z3

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

Cost: 11M + 1S + 2*a + 14add + 1*2.
Cost: 11M + 1S + 2*a + 13add + 1*2 dependent upon the first point.
Source: 2008.02.25 Hisil–Wong–Carter–Dawson, page 6.
Strongly unified.

Explicit formulas:

      E = S1*D2
      F = C1*Z2
      G = D1*S2
      H = Z1*C2
      J = SC1*DZ2
      K = DZ1*SC2
      S3 = (H+F)*(E+G)-J-K
      C3 = (H+E)*(F-G)-J+K
      D3 = (DZ1-a*SC1)*(SC2+DZ2)+a*J-K
      Z3 = (H+G)^²-2*K
      SC3 = S3*C3
      DZ3 = D3*Z3

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

Assumptions: Z2=1.
Cost: 13M + 2S + 1*a + 7add.
Cost: 12M + 2S + 1*a + 7add dependent upon the first point.
Source: 2001 Liardet–Smart "Preventing SPA/DPA in ECC systems using the Jacobi form", plus substitution Z2=1.
Strongly unified.

Explicit formulas:

      Z1C2 = Z1*C2
      S1D2 = S1*D2
      D1S2 = D1*S2
      U = Z1C2*C1
      V = D1S2*S1D2
      S3 = (Z1C2+D1S2)*(C1+S1D2)-U-V
      C3 = U-V
      D3 = Z1*D1*D2-a*S1*C1*S2*C2
      Z3 = Z1C2^²+D1S2^²
      SC3 = S3*C3
      DZ3 = D3*Z3

The "smadd-2001-ls" addition formulas [database entry; Sage verification script; Sage output; three-operand code]:

Assumptions: S2=1.
Cost: 13M + 2S + 1*a + 7add.
Cost: 12M + 2S + 1*a + 7add dependent upon the first point.
Source: 2001 Liardet–Smart "Preventing SPA/DPA in ECC systems using the Jacobi form", plus substitution S2=1 (as suggested by 2007 Hisil–Carter–Dawson).
Strongly unified.

Explicit formulas:

      Z2D2 = Z2*D2
      E = Z1*C2
      F = S1*D2
      G = C1*Z2
      H = E*G
      J = D1*F
      S3 = (E+D1)*(G+F)-H-J
      C3 = H-J
      D3 = Z1*D1*Z2D2-a*S1*C1*C2
      Z3 = E^²+D1^²
      SC3 = S3*C3
      DZ3 = D3*Z3

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

Cost: 15M + 2S + 1*a + 7add.
Cost: 13M + 2S + 1*a + 7add dependent upon the first point.
Source: 2001 Liardet–Smart "Preventing SPA/DPA in ECC systems using the Jacobi form".
Strongly unified.

Explicit formulas:

      Z1C2 = Z1*C2
      S1D2 = S1*D2
      D1S2 = D1*S2
      C1Z2 = C1*Z2
      U = Z1C2*C1Z2
      V = D1S2*S1D2
      S3 = (Z1C2+D1S2)*(C1Z2+S1D2)-U-V
      C3 = U-V
      D3 = Z1*D1*Z2*D2-a*S1*C1*S2*C2
      Z3 = Z1C2^²+D1S2^²
      SC3 = S3*C3
      DZ3 = D3*Z3

The "add-1986-cc-2" addition formulas [database entry; Sage verification script; Sage output; three-operand code]:

Cost: 16M + 2S + 1*a + 4add.
Cost: 14M + 2S + 1*a + 4add dependent upon the first point.
Source: 1986 Chudnovsky–Chudnovsky "Sequences of numbers generated by addition in formal groups and new primality and factorization tests", formula (4.9i), plus common-subexpression elimination.
Strongly unified.

Explicit formulas:

      Z1C2 = Z1*C2
      S1D2 = S1*D2
      D1S2 = D1*S2
      C1Z2 = C1*Z2
      S3 = Z1C2*S1D2+D1S2*C1Z2
      C3 = Z1C2*C1Z2-D1S2*S1D2
      D3 = Z1*D1*Z2*D2-a*S1*C1*S2*C2
      Z3 = Z1C2^²+D1S2^²
      SC3 = S3*C3
      DZ3 = D3*Z3

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

Cost: 22M + 2S + 1*a + 4add.
Cost: 20M + 2S + 1*a + 4add dependent upon the first point.
Source: 1986 Chudnovsky–Chudnovsky "Sequences of numbers generated by addition in formal groups and new primality and factorization tests", formula (4.9i).
Strongly unified.

Explicit formulas:

      S3 = Z1*C2*S1*D2+D1*S2*C1*Z2
      C3 = Z1*C2*C1*Z2-D1*S2*S1*D2
      D3 = Z1*D1*Z2*D2-a*S1*C1*S2*C2
      Z3 = (Z1*C2)^²+(D1*S2)^²
      SC3 = S3*C3
      DZ3 = D3*Z3

Explicit formulas for doubling

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

Cost: 2M + 5S + 1*a + 7add + 1*2.
Source: 2008.02.25 Hisil–Wong–Carter–Dawson.

Explicit formulas:

      E = DZ1^²
      F = SC1^²
      G = a*F
      Z3 = E+G
      D3 = E-G
      CC1 = C1^²
      C3 = 2*(F+CC1^²)-Z3
      S3 = (SC1+DZ1)^²-E-F
      SC3 = S3*C3
      DZ3 = D3*Z3

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

Assumptions: Z1=1.
Cost: 4M + 4S + 5add + 1*2.
Source: 2007 Bernstein–Lange.

Explicit formulas:

      a0 = S1
      a1 = C1
      a2 = D1
      m = a1^²
      l2 = a0*a2
      n = l2^²
      l3 = 2*(a1*a2)^²
      r3 = m+n
      r0 = (a1+l2)^²-r3
      r1 = m-n
      r2 = l3-r1
      S3 = r0
      C3 = r1
      D3 = r2
      Z3 = r3
      SC3 = S3*C3
      DZ3 = D3*Z3

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

Cost: 5M + 4S + 5add + 1*2.
Source: 2007 Bernstein–Lange.

Explicit formulas:

      a0 = S1
      a1 = C1
      a2 = D1
      a3 = Z1
      l1 = a3*a1
      m = l1^²
      l2 = a0*a2
      n = l2^²
      l3 = 2*(a1*a2)^²
      r3 = m+n
      r0 = (l1+l2)^²-r3
      r1 = m-n
      r2 = l3-r1
      S3 = r0
      C3 = r1
      D3 = r2
      Z3 = r3
      SC3 = S3*C3
      DZ3 = D3*Z3

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

Cost: 6M + 3S + 5add + 3*2.
Source: 2001 Liardet–Smart "Preventing SPA/DPA in ECC systems using the Jacobi form".

Explicit formulas:

      a0 = S1
      a1 = C1
      a2 = D1
      a3 = Z1
      l1 = a3*a1
      l2 = a0*a2
      l3 = 2*(a1*a2)^²
      r0 = 2*l1*l2
      r3 = (l1+l2)^²-r0
      r1 = r3-2*l2^²
      r2 = -r1+l3
      S3 = r0
      C3 = r1
      D3 = r2
      Z3 = r3
      SC3 = S3*C3
      DZ3 = D3*Z3

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

Cost: 7M + 3S + 5add + 1*2.
Source: 1986 Chudnovsky–Chudnovsky "Sequences of numbers generated by addition in formal groups and new primality and factorization tests", formula 4.9ii, plus common-subexpression elimination.

Explicit formulas:

      C1Z1 = C1*Z1
      C1D1 = C1*D1
      D1Z1 = D1*Z1
      D1S1 = D1*S1
      U = C1Z1^²
      V = C1D1^²
      W = D1Z1^²
      UV = U-V
      S3 = 2*C1Z1*D1S1
      C3 = U-W+V
      D3 = W-UV
      Z3 = W+UV
      SC3 = S3*C3
      DZ3 = D3*Z3

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

Cost: 14M + 9S + 6add + 1*2.
Source: 1986 Chudnovsky–Chudnovsky "Sequences of numbers generated by addition in formal groups and new primality and factorization tests", formula 4.9ii.

Explicit formulas:

      S3 = 2*C1*Z1*D1*S1
      C3 = (C1*Z1)^²-(D1*Z1)^²+(C1*D1)^²
      D3 = (D1*Z1)^²-(C1*Z1)^²+(C1*D1)^²
      Z3 = (D1*Z1)^²+(C1*Z1)^²-(C1*D1)^²
      SC3 = S3*C3
      DZ3 = D3*Z3

Explicit formulas for tripling

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

Assumptions: b=a-1 and b2=2*b and b3=3*b and bb2=2*b*b.
Cost: 6M + 10S + 1*bb2 + 1*b2 + 2*a + 1*b3 + 21add + 4*2.
Source: 2007 Hisil–Carter–Dawson, plus common-subexpression elimination.

Explicit formulas:

      E = S1^²
      F = C1^²
      G = E^²
      H = F^²
      J = G^²
      K = H^²
      L = (E+F)^²-H-G
      M = L^²
      N = (G+L)^²-J-M
      P = (H+L)^²-K-M
      R = bb2*J
      Q = b2*N
      T = b3*M
      U = 2*P
      V = 2*K
      W = a*U
      Y = a*Q
      RV = R-V
      RQ = R-Q
      UV = U+V
      TW = T+W
      TY = T-Y
      RQUV = RQ+UV
      S3 = S1*(RV+TW-2*UV)
      C3 = C1*(RV-TY+2*RQ)
      D3 = D1*(TW-RQUV)
      Z3 = Z1*(TY-RQUV)
      SC3 = S3*C3
      DZ3 = D3*Z3

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

Assumptions: b=a-1 and b2=2*b and bb2=2*b*b and b3=3*b.
Cost: 6M + 10S + 1*bb2 + 1*b2 + 2*a + 1*b3 + 29add + 4*2.
Source: 2007 Hisil–Carter–Dawson.

Explicit formulas:

      E = S1^²
      F = C1^²
      G = E^²
      H = F^²
      J = G^²
      K = H^²
      L = (E+F)^²-H-G
      M = L^²
      N = (G+L)^²-J-M
      P = (H+L)^²-K-M
      R = bb2*J
      Q = b2*N
      T = b3*M
      U = 2*P
      V = 2*K
      W = a*U
      Y = a*Q
      S3 = S1*((R-V)+(T+W)-2*(U+V))
      C3 = C1*((R-V)-(T-Y)+2*(R-Q))
      D3 = D1*((T+W)-(R-Q)-(U+V))
      Z3 = Z1*((T-Y)-(R-Q)-(U+V))
      SC3 = S3*C3
      DZ3 = D3*Z3

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

Assumptions: b=a-1.
Cost: 9M + 7S + 3*b + 16add + 4*2.
Source: 2007 Hisil–Carter–Dawson.

Explicit formulas:

      R0 = S1^²
      R1 = C1^²
      R2 = R0^²
      R3 = R1^²
      R4 = 2*R3
      R5 = 2*R4
      R6 = 2*R1
      R6 = R6+R0
      R6 = R6^²
      R6 = R6-R2
      R6 = R6-R5
      R2 = b*R2
      R5 = R5+R4
      R4 = R2^²
      R0 = R5*R2
      R5 = R2*R6
      R2 = R3^²
      R1 = R3*R6
      R3 = R4-R2
      R2 = R4+R2
      R4 = 2*R3
      R3 = b*R1
      R6 = b*R5
      R3 = R0+R3
      R1 = R1+R2
      R0 = R0-R6
      R2 = R5-R2
      R5 = R3+R4
      R5 = R5-R1
      S3 = S1*R5
      R4 = R4-R2
      R4 = R4-R0
      C3 = C1*R4
      R2 = R2+R3
      D3 = D1*R2
      R0 = R0-R1
      Z3 = Z1*R0
      SC3 = S3*C3
      DZ3 = D3*Z3

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

Assumptions: b=a-1.
Cost: 9M + 7S + 5*b + 24add + 5*2.
Source: 2007 Hisil–Carter–Dawson.

Explicit formulas:

      E = S1^²
      F = C1^²
      G = E^²
      H = F^²
      J = 2*H
      K = 2*J
      L = (2*F+E)^²-G-K
      M = b*G
      N = K+J
      P = M^²
      R = N*M
      U = M*L
      V = H^²
      W = H*L
      S3 = S1*(R+b*W+2*(P-V)-W-P-V)
      C3 = C1*(2*(P-V)-U+P+V-R+b*U)
      D3 = D1*(U-P-V+R+b*W)
      Z3 = Z1*(R-b*U-W-P-V)
      SC3 = S3*C3
      DZ3 = D3*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 + 4M + 0add.

Explicit formulas:

      A = 1/Z1
      S3 = S1*A
      C3 = C1*A
      D3 = D1*A
      Z3 = 1
      SC3 = S3*C3
      DZ3 = D3