Projective coordinates for Edwards curves (original) (raw)

Explicit-Formulas Database
Genus-1 curves over large-characteristic fields
Edwards curves EFD / Genus-1 large-characteristic / Projective coordinates for Edwards curvesAn 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+dx^2y^2)

Projective coordinates [database entry] represent x y as X Y Z satisfying the following equations:

x=X/Z y=Y/Z

Best operation counts

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

11M for addition: 10M+1S. 10M+1S. 10M+1S. 11M.
10M for addition with X2=1: 9M+1S.
9M for addition with Z2=1: 9M.
7M for addition with Z1=1 and Z2=1: 6M+1S.
11M for readdition: 10M+1S after 10M+1S. 10M+1S after 10M+1S. 10M+1S after 10M+1S. 11M after 11M. 9M+2S after 10M+3S.
10M for readdition with X2=1: 9M+1S after 9M+1S.
9M for readdition with Z2=1: 9M after 9M.
7M for readdition with Z1=1 and Z2=1: 6M+1S after 6M+1S.
7M for doubling: 3M+4S. 3M+4S. 3M+4S.
6M for doubling with Z1=1: 3M+3S.
13M for tripling: 9M+4S. 9M+4S.
102M for scaling: 1I+2M. Smallest multiplication counts assuming I=100M, S=0.8M, *param=0M, add=0M, *const=0M:
10.8M for addition: 10M+1S. 10M+1S. 10M+1S.
9.8M for addition with X2=1: 9M+1S.
9M for addition with Z2=1: 9M.
6.8M for addition with Z1=1 and Z2=1: 6M+1S.
10.6M for readdition: 9M+2S after 10M+3S.
9.8M for readdition with X2=1: 9M+1S after 9M+1S.
9M for readdition with Z2=1: 9M after 9M.
6.8M for readdition with Z1=1 and Z2=1: 6M+1S after 6M+1S.
6.2M for doubling: 3M+4S. 3M+4S. 3M+4S.
5.4M for doubling with Z1=1: 3M+3S.
12.2M for tripling: 9M+4S. 9M+4S.
102M for scaling: 1I+2M. Smallest multiplication counts assuming I=100M, S=0.67M, *param=0M, add=0M, *const=0M:
10.35M for addition: 7M+5S.
9.67M for addition with X2=1: 9M+1S.
9M for addition with Z2=1: 9M.
6.67M for addition with Z1=1 and Z2=1: 6M+1S.
10.34M for readdition: 9M+2S after 10M+3S.
9.67M for readdition with X2=1: 9M+1S after 9M+1S.
9M for readdition with Z2=1: 9M after 9M.
6.67M for readdition with Z1=1 and Z2=1: 6M+1S after 6M+1S.
5.68M for doubling: 3M+4S. 3M+4S. 3M+4S.
5.01M for doubling with Z1=1: 3M+3S.
11.68M for tripling: 9M+4S. 9M+4S.
102M for scaling: 1I+2M.

Summary of all explicit formulas

Operation	Assumptions	Cost	Readdition cost
addition	Z1=1 and Z2=1	6M + 1S + 1c + 1d	6M + 1S + 1c + 1d
addition	k*c=1 and Z2=1	9M + 1*k	9M + 1*k
addition	X2=1	9M + 1S + 1c + 1d	9M + 1S + 1c + 1d
addition	Z2=1	9M + 1S + 1c + 1d	9M + 1S + 1c + 1d
addition	Z2=1	9M + 1S + 1c + 1d	9M + 1S + 1c + 1d
addition	c2=2*c and Z2=1	6M + 5S + 1c2 + 1d	6M + 5S + 1c2 + 1d
addition	10M + 1S + 1c + 1d	10M + 1S + 1c + 1d
addition	10M + 1S + 1c + 1d	10M + 1S + 1c + 1d
addition	i^2=-1	10M + 1S + 3i + 1c + 1*d	10M + 1S + 2i + 1c + 1*d
addition	k*c=1	11M + 1*k	11M + 1*k
addition	c2=2*c	7M + 5S + 1c2 + 1d	7M + 5S + 1c2 + 1d
addition	k*c=1	10M + 3S + 1*k	9M + 2S + 1*k
doubling	cc2=2cc and Z1=1	3M + 3S + 2*c
doubling	3M + 4S + 3*c
doubling	3M + 4S + 3*c
doubling	3M + 4S + 3*c
tripling	c2=2*c	9M + 4S + 1*c2
tripling	9M + 4S + 1*c
tripling	c=1	7M + 7S
tripling	cc4=4cc	7M + 7S + 1*cc4
scaling	1I + 2M

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: 6M + 1S + 1*c + 1*d + 8add.
Cost: 6M + 1S + 1*c + 1*d + 7add dependent upon the first point.
Source: 2007 Bernstein–Lange.
Strongly unified.
Explicit formulas:
C = X1X2
D = Y1Y2
E = dCD
X3 = (1-E)((X1+Y1)(X2+Y2)-C-D)
Y3 = (1+E)(D-C)
Z3 = c(1-E^2)

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

Assumptions: k*c=1 and Z2=1.
Cost: 9M + 1*k + 8add.
Source: 2008.02.25 Hisil–Wong–Carter–Dawson, page 8.
Explicit formulas:
A = X1
B = Y1
C = Z1X2
D = Z1Y2
E = AB
F = CD
G = E+F
H = E-F
J = (A-C)(B+D)-H
K = (A+D)(B+C)-G
X3 = GJ
Y3 = HK
Z3 = kJK

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

Assumptions: X2=1.
Cost: 9M + 1S + 1*c + 1*d + 4add.
Source: 2007 Hisil–Carter–Dawson.
Strongly unified.
Explicit formulas:
T0 = X1Y2
T0 = T0+Y1
Y3 = Y1Y2
T1 = Y3X1
Y3 = Y3-X1
Z3 = Z1Z2
X3 = T0Z3
Y3 = Y3Z3
T1 = dT1
Z3 = Z3^2
T0 = Z3-T1
Z3 = Z3+T1
X3 = X3T0
Y3 = Y3Z3
Z3 = Z3T0
Z3 = c*Z3

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

Assumptions: Z2=1.
Cost: 9M + 1S + 1*c + 1*d + 7add.
Cost: 9M + 1S + 1*c + 1*d + 6add dependent upon the first point.
Source: 2007 Bernstein–Lange.
Strongly unified.
Explicit formulas:
R1 = X1
R2 = Y1
R3 = Z1
R4 = X2
R5 = Y2
R7 = R1+R2
R6 = R4+R5
R1 = R1R4
R2 = R2R5
R7 = R7R6
R7 = R7-R1
R7 = R7-R2
R7 = R7R3
R6 = R1R2
R6 = dR6
R2 = R2-R1
R2 = R2R3
R3 = R3^2
R1 = R3-R6
R3 = R3+R6
R2 = R2R3
R3 = R3R1
R1 = R1R7
R3 = c*R3
X3 = R1
Y3 = R2
Z3 = R3

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

Assumptions: Z2=1.
Cost: 9M + 1S + 1*c + 1*d + 7add.
Cost: 9M + 1S + 1*c + 1*d + 6add dependent upon the first point.
Source: 2007 Bernstein–Lange.
Strongly unified.
Explicit formulas:
B = Z1^2
C = X1X2
D = Y1Y2
E = dCD
F = B-E
G = B+E
X3 = Z1F((X1+Y1)(X2+Y2)-C-D)
Y3 = Z1G*(D-C)
Z3 = cFG

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

Assumptions: c2=2*c and Z2=1.
Cost: 6M + 5S + 1*c2 + 1*d + 13add + 1*2.
Cost: 6M + 5S + 1*c2 + 1*d + 12add + 1*2 dependent upon the first point.
Source: 2007 Bernstein–Lange.
Strongly unified.
Explicit formulas:
B = Z1^2
C = X1X2
D = Y1Y2
E = dCD
BB = B^2
EE = E^2
H = (Z1+B)^2-BB
I = (Z1+E)^2-EE
X3 = (H-I)((X1+Y1)(X2+Y2)-C-D)
Y3 = (H+I-2B)(D-C)
Z3 = c2*(BB-EE)

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

Cost: 10M + 1S + 1*c + 1*d + 7add.
Cost: 10M + 1S + 1*c + 1*d + 6add dependent upon the first point.
Source: 2007 Bernstein–Lange.
Strongly unified.
Explicit formulas:
R1 = X1
R2 = Y1
R3 = Z1
R4 = X2
R5 = Y2
R6 = Z2
R3 = R3R6
R7 = R1+R2
R8 = R4+R5
R1 = R1R4
R2 = R2R5
R7 = R7R8
R7 = R7-R1
R7 = R7-R2
R7 = R7R3
R8 = R1R2
R8 = dR8
R2 = R2-R1
R2 = R2R3
R3 = R3^2
R1 = R3-R8
R3 = R3+R8
R2 = R2R3
R3 = R3R1
R1 = R1R7
R3 = cR3
X3 = R1
Y3 = R2
Z3 = R3

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

Cost: 10M + 1S + 1*c + 1*d + 7add.
Cost: 10M + 1S + 1*c + 1*d + 6add dependent upon the first point.
Source: 2007 Bernstein–Lange.
Strongly unified.
Explicit formulas:
A = Z1Z2
B = A^2
C = X1X2
D = Y1Y2
E = dCD
F = B-E
G = B+E
X3 = AF*((X1+Y1)(X2+Y2)-C-D)
Y3 = AG*(D-C)
Z3 = cFG

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

Assumptions: i^2=-1.
Cost: 10M + 1S + 3*i + 1*c + 1*d + 9add + 2*2.
Cost: 10M + 1S + 2*i + 1*c + 1*d + 7add + 2*2 dependent upon the first point.
Source: 2007 Bernstein–Lange.
Strongly unified.
Explicit formulas:
iX2 = iX2
C2 = Y2+iX2
D2 = Y2-iX2
iX1 = iX1
C1 = Y1+iX1
D1 = Y1-iX1
A = Z1Z2
B = 2A^2
C = C1C2
D = D1D2
L = D+C
M = Y1Y2
N = 2M-L
E = dMN
F = B-E
G = B+E
X3 = iAF*(D-C)
Y3 = AGL
Z3 = cGF

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

Assumptions: k*c=1.
Cost: 11M + 1*k + 8add.
Source: 2008.02.25 Hisil–Wong–Carter–Dawson, page 8.
Explicit formulas:
A = X1Z2
B = Y1Z2
C = Z1X2
D = Z1Y2
E = AB
F = CD
G = E+F
H = E-F
J = (A-C)(B+D)-H
K = (A+D)(B+C)-G
X3 = GJ
Y3 = HK
Z3 = kJK

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

Assumptions: c2=2*c.
Cost: 7M + 5S + 1*c2 + 1*d + 13add + 1*2.
Cost: 7M + 5S + 1*c2 + 1*d + 12add + 1*2 dependent upon the first point.
Source: 2007 Bernstein–Lange.
Strongly unified.
Explicit formulas:
A = Z1Z2
B = A^2
C = X1X2
D = Y1Y2
E = dCD
BB = B^2
EE = E^2
H = (A+B)^2-BB
I = (A+E)^2-EE
X3 = (H-I)((X1+Y1)(X2+Y2)-C-D)
Y3 = (H+I-2B)(D-C)
Z3 = c2(BB-EE)

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

Assumptions: k*c=1.
Cost: 10M + 3S + 1*k + 13add + 2*2.
Cost: 9M + 2S + 1*k + 13add + 2*2 dependent upon the first point.
Source: 2009.03.11 Hisil–Wong–Carter–Dawson, after formula (17), plus denominator elimination.
Explicit formulas:
R1 = X2Y2
R2 = Z2^2
A = X1Y1
B = Z1^2
C = R2A
D = R1B
E = (X1-X2)(Y1+Y2)-A+R1
F = (X1+Y2)(Y1+X2)-A-R1
G = (Z1+Z2)^2-B-R2
X3 = 2E(C+D)
Y3 = 2F(C-D)
Z3 = kEF*G

Explicit formulas for doubling

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

Assumptions: cc2=2*c*c and Z1=1.
Cost: 3M + 3S + 2*c + 5add.
Source: 2007 Bernstein–Lange.
Explicit formulas:
B = (X1+Y1)^2
C = X1^2
D = Y1^2
E = C+D
J = E-cc2
X3 = c*(B-E)J
Y3 = cE*(C-D)
Z3 = E*J

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

Cost: 3M + 4S + 3*c + 5add + 1*2.
Source: 2007 Bernstein–Lange; source comments that these formulas use two temporary registers.
Explicit formulas:
R1 = X1
R2 = Y1
R3 = Z1
R4 = R1+R2
R3 = cR3
R1 = R1^2
R2 = R2^2
R3 = R3^2
R4 = R4^2
R3 = 2R3
R5 = R1+R2
R2 = R1-R2
R4 = R4-R5
R3 = R5-R3
R1 = R3R4
R3 = R3R5
R2 = R2R5
R1 = cR1
R2 = c*R2
X3 = R1
Y3 = R2
Z3 = R3

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

Cost: 3M + 4S + 3*c + 5add + 1*2.
Source: 2007 Bernstein–Lange.
Explicit formulas:
B = (X1+Y1)^2
C = X1^2
D = Y1^2
E = C+D
H = (cZ1)^2
J = E-2H
X3 = c*(B-E)J
Y3 = cE*(C-D)
Z3 = E*J

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

Cost: 3M + 4S + 3*c + 5add + 2*2.
Source: 2007 Bernstein–Lange; source comments that these formulas use one temporary register.
Explicit formulas:
R1 = X1
R2 = Y1
R3 = Z1
R3 = cR3
R4 = R1^2
R1 = R1+R2
R1 = R1^2
R2 = R2^2
R3 = R3^2
R3 = 2R3
R4 = R2+R4
R2 = 2R2
R2 = R4-R2
R1 = R1-R4
R2 = R2R4
R3 = R4-R3
R1 = R1R3
R3 = R3R4
R1 = cR1
R2 = cR2
X3 = R1
Y3 = R2
Z3 = R3

Explicit formulas for tripling

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

Assumptions: c2=2*c.
Cost: 9M + 4S + 1*c2 + 6add + 1*2.
Source: 2007 Bernstein–Birkner–Lange–Peters.
Explicit formulas:
XX = X1^2
YY = Y1^2
ZZ = (c2Z1)^2
D = XX+YY
DD = D^2
H = 2D*(XX-YY)
P = DD-YYZZ
Q = DD-XXZZ
T = H+Q
U = H-P
X3 = PUX1
Y3 = QTY1
Z3 = TUZ1

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

Cost: 9M + 4S + 1*c + 13add + 2*2.
Source: 2007 Hisil–Carter–Dawson.
Explicit formulas:
A = X1^2
B = Y1^2
C = (2cZ1)^2
D = (A+B)^2
E = 2*(A+B)(A-B)
F = AC
G = BC
X3 = X1(E-(D-G))(D-G)
Y3 = Y1(E+(D-F))(D-F)
Z3 = Z1(E-(D-G))*(E+(D-F))

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

Assumptions: c=1.
Cost: 7M + 7S + 12add + 2*2 + 1*4.
Source: 2007 Bernstein–Birkner–Lange–Peters.
Explicit formulas:
XX = X1^2
YY = Y1^2
ZZ = Z1^2
ZZ4 = 4ZZ
D = XX+YY
DD = D^2
H = 2D*(XX-YY)
P = DD-YYZZ4
Q = DD-XXZZ4
T = H+Q
TT = T^2
U = H-P
X3 = 2PUX1
Y3 = Q((T+Y1)^2-TT-YY)
Z3 = U*((T+Z1)^2-TT-ZZ)

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

Assumptions: cc4=4*c*c.
Cost: 7M + 7S + 1*cc4 + 12add + 2*2.
Source: 2007 Bernstein–Birkner–Lange–Peters.
Explicit formulas:
XX = X1^2
YY = Y1^2
ZZ = Z1^2
ZZ4 = cc4ZZ
D = XX+YY
DD = D^2
H = 2D*(XX-YY)
P = DD-YYZZ4
Q = DD-XXZZ4
T = H+Q
TT = T^2
U = H-P
X3 = 2PUX1
Y3 = Q((T+Y1)^2-TT-YY)
Z3 = U*((T+Z1)^2-TT-ZZ)

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 + 0add.
Explicit formulas:
A = 1/Z1
X3 = X1A
Y3 = Y1A
Z3 = 1