Speed records:
The following commands for the Magma computer-algebra system check various addition formulas for projective coordinates.
Projective scaling.
K<a,b,X1,Y1>:=FieldOfFractions(PolynomialRing(Rationals(),4));
R<Z1>:=PolynomialRing(K,1);
S:=quo<R|Y1^2*Z1-X1^3-a*X1*Z1^2-b*Z1^3>;
// here are the formulas:
A:=1/Z1;
X2:=A*X1;
Y2:=A*Y1;
Z2:=1;
// check:
x1:=X1/Z1; y1:=Y1/Z1;
S!(y1^2-x1^3-a*x1-b);
x2:=X2/Z2; y2:=Y2/Z2;
S!(y2^2-x2^3-a*x2-b);
S!(Z2-1);
S!(x2-x1); S!(y2-y1);
Projective addition (12M+2S+6add+1times2) matches affine addition. Multiplication counts stated in the literature: 14 in 1986 Chudnovsky/Chudnovsky, page 415, formula (4.4i) ("14 multiplications"). 14 in 1998 Cohen/Miyaji/Ono. 14 in 2004 Hankerson/Menezes/Vanstone, page 92. 14 in 2005 Doche/Lange. 14 in 2007 Bernstein/Lange.
S,M counts stated in the literature: 12M+2S in 1998 Cohen/Miyaji/Ono, formula (3). 12M+2S in 2004 Hankerson/Menezes/Vanstone, page 92. 12M+2S in 2005 Doche/Lange. 12M+2S in 2007 Bernstein/Lange.
1986 Chudnovsky/Chudnovsky, page 415, formula (4.4i):
K<a,b,X1,Y1,X2,Y2>:=FieldOfFractions(PolynomialRing(Rationals(),6));
R<Z1,Z2>:=PolynomialRing(K,2);
S:=quo<R|Y1^2*Z1-X1^3-a*X1*Z1^2-b*Z1^3,Y2^2*Z2-X2^3-a*X2*Z2^2-b*Z2^3>;
x1:=X1/Z1; y1:=Y1/Z1;
S!(y1^2-x1^3-a*x1-b);
x2:=X2/Z2; y2:=Y2/Z2;
S!(y2^2-x2^3-a*x2-b);
lambda:=(y2-y1)/(x2-x1);
x3:=lambda^2-x1-x2; y3:=lambda*(x1-x3)-y1;
S!(y3^2-x3^3-a*x3-b);
// here are the formulas:
U1:=X1*Z2;
U2:=X2*Z1;
S1:=Y1*Z2;
S2:=Y2*Z1;
W:=Z1*Z2;
P:=U2-U1;
R:=S2-S1;
X3:=P*(-(U1+U2)*P^2+W*R^2);
Y3:=(R*(-2*W*R^2+3*(U1+U2)*P^2)-P^3*(S1+S2))/2;
Z3:=W*P^3;
S!(x3-X3/Z3); S!(y3-Y3/Z3);
1998 Cohen/Miyaji/Ono, formula (3), reported as "12M + 2S":
K<a,b,X1,Y1,X2,Y2>:=FieldOfFractions(PolynomialRing(Rationals(),6));
R<Z1,Z2>:=PolynomialRing(K,2);
S:=quo<R|Y1^2*Z1-X1^3-a*X1*Z1^2-b*Z1^3,Y2^2*Z2-X2^3-a*X2*Z2^2-b*Z2^3>;
x1:=X1/Z1; y1:=Y1/Z1;
x2:=X2/Z2; y2:=Y2/Z2;
lambda:=(y2-y1)/(x2-x1);
x3:=lambda^2-x1-x2; y3:=lambda*(x1-x3)-y1;
// here are the formulas:
u:=Y2*Z1-Y1*Z2;
v:=X2*Z1-X1*Z2;
A:=u^2*Z1*Z2-v^3-2*v^2*X1*Z2;
X3:=v*A;
Y3:=u*(v^2*X1*Z2-A)-v^3*Y1*Z2;
Z3:=v^3*Z1*Z2;
S!(x3-X3/Z3); S!(y3-Y3/Z3);
Eliminating common subexpressions from 1998 Cohen/Miyaji/Ono,
12M + 2S + 6add + 1times2:
K<a,b,X1,Y1,X2,Y2>:=FieldOfFractions(PolynomialRing(Rationals(),6));
R<Z1,Z2>:=PolynomialRing(K,2);
S:=quo<R|Y1^2*Z1-X1^3-a*X1*Z1^2-b*Z1^3,Y2^2*Z2-X2^3-a*X2*Z2^2-b*Z2^3>;
x1:=X1/Z1; y1:=Y1/Z1;
x2:=X2/Z2; y2:=Y2/Z2;
lambda:=(y2-y1)/(x2-x1);
x3:=lambda^2-x1-x2; y3:=lambda*(x1-x3)-y1;
// here are the formulas:
Y1Z2:=Y1*Z2;
X1Z2:=X1*Z2;
Z1Z2:=Z1*Z2;
u:=Y2*Z1-Y1Z2;
uu:=u^2;
v:=X2*Z1-X1Z2;
vv:=v^2;
vvv:=v*vv;
R:=vv*X1Z2;
A:=uu*Z1Z2-vvv-2*R;
X3:=v*A;
Y3:=u*(R-A)-vvv*Y1Z2;
Z3:=vvv*Z1Z2;
S!(x3-X3/Z3); S!(y3-Y3/Z3);
Projective mixed addition (9M+2S+6add+1imes2) matches affine addition. Eliminating common subexpressions from 1998 Cohen/Miyaji/Ono and substituting Z2=1, 9M + 2S + 6add + 1times2, matching "9M + 2S" stated in 2005 Doche/Lange:
K<a,b,X1,Y1,X2>:=FieldOfFractions(PolynomialRing(Rationals(),5));
R<Z1,Y2>:=PolynomialRing(K,2);
Z2:=1;
S:=quo<R|Y1^2*Z1-X1^3-a*X1*Z1^2-b*Z1^3,Y2^2*Z2-X2^3-a*X2*Z2^2-b*Z2^3>;
x1:=X1/Z1; y1:=Y1/Z1;
x2:=X2/Z2; y2:=Y2/Z2;
lambda:=(y2-y1)/(x2-x1);
x3:=lambda^2-x1-x2; y3:=lambda*(x1-x3)-y1;
// here are the formulas:
u:=Y2*Z1-Y1;
uu:=u^2;
v:=X2*Z1-X1;
vv:=v^2;
vvv:=v*vv;
R:=vv*X1;
A:=uu*Z1-vvv-2*R;
X3:=v*A;
Y3:=u*(R-A)-vvv*Y1;
Z3:=vvv*Z1;
S!(x3-X3/Z3); S!(y3-Y3/Z3);
Projective unified addition (11M+6S+1D+10add+4times2+1times4) matches affine addition. 2002 Brier Joye, page 339, 12M + 5S + 1D + 7add + 3times2 (reported as "17 multiplications plus 1 multiplication by constant"), strongly unified:
K<a,b,X1,Y1,X2,Y2>:=FieldOfFractions(PolynomialRing(Rationals(),6));
R<Z1,Z2>:=PolynomialRing(K,2);
SS:=quo<R|Y1^2*Z1-X1^3-a*X1*Z1^2-b*Z1^3,Y2^2*Z2-X2^3-a*X2*Z2^2-b*Z2^3>;
x1:=X1/Z1; y1:=Y1/Z1;
x2:=X2/Z2; y2:=Y2/Z2;
lambda:=(y2-y1)/(x2-x1);
x3:=lambda^2-x1-x2; y3:=lambda*(x1-x3)-y1;
// here are the formulas:
U1:=X1*Z2;
U2:=X2*Z1;
S1:=Y1*Z2;
S2:=Y2*Z1;
Z:=Z1*Z2;
T:=U1+U2;
M:=S1+S2;
R:=T^2-U1*U2+a*Z^2;
F:=Z*M;
L:=M*F;
G:=T*L;
W:=R^2-G;
X3:=2*F*W;
Y3:=R*(G-2*W)-L^2;
Z3:=2*F*F^2;
SS!(x3-X3/Z3); SS!(y3-Y3/Z3);
2007 Bernstein/Lange, 11M + 6S + 1D + 10add + 4times2 + 1times4, strongly unified:
K<a,b,X1,Y1,X2,Y2>:=FieldOfFractions(PolynomialRing(Rationals(),6));
R<Z1,Z2>:=PolynomialRing(K,2);
SS:=quo<R|Y1^2*Z1-X1^3-a*X1*Z1^2-b*Z1^3,Y2^2*Z2-X2^3-a*X2*Z2^2-b*Z2^3>;
x1:=X1/Z1; y1:=Y1/Z1;
x2:=X2/Z2; y2:=Y2/Z2;
lambda:=(y2-y1)/(x2-x1);
x3:=lambda^2-x1-x2; y3:=lambda*(x1-x3)-y1;
// here are the formulas:
U1:=X1*Z2;
U2:=X2*Z1;
S1:=Y1*Z2;
S2:=Y2*Z1;
Z:=Z1*Z2;
T:=U1+U2;
TT:=T^2;
M:=S1+S2;
R:=TT-U1*U2+a*Z^2;
F:=Z*M;
L:=M*F;
LL:=L^2;
G:=(T+L)^2-TT-LL;
W:=2*R^2-G;
X3:=2*F*W;
Y3:=R*(G-2*W)-2*LL;
Z3:=4*F*F^2;
SS!(x3-X3/Z3); SS!(y3-Y3/Z3);
Projective unified addition for a=-1 (13M+3S+8add+3times2) matches affine addition. 2002 Brier Joye, page 340, 13M + 3S + 8add + 3times2 in the special case a = -1, strongly unified:
K<b,X1,Y1,X2,Y2>:=FieldOfFractions(PolynomialRing(Rationals(),5));
a:=-1;
R<Z1,Z2>:=PolynomialRing(K,2);
SS:=quo<R|Y1^2*Z1-X1^3-a*X1*Z1^2-b*Z1^3,Y2^2*Z2-X2^3-a*X2*Z2^2-b*Z2^3>;
x1:=X1/Z1; y1:=Y1/Z1;
x2:=X2/Z2; y2:=Y2/Z2;
lambda:=(y2-y1)/(x2-x1);
x3:=lambda^2-x1-x2; y3:=lambda*(x1-x3)-y1;
// here are the formulas:
U1:=X1*Z2;
U2:=X2*Z1;
S1:=Y1*Z2;
S2:=Y2*Z1;
Z:=Z1*Z2;
T:=U1+U2;
M:=S1+S2;
R:=(T-Z)*(T+Z)-U1*U2;
F:=Z*M;
L:=M*F;
G:=T*L;
W:=R^2-G;
X3:=2*F*W;
Y3:=R*(G-2*W)-L^2;
Z3:=2*F*F^2;
SS!(x3-X3/Z3); SS!(y3-Y3/Z3);
Projective addition with Z1=1 and Z2=1. Eliminating common subexpressions from 1998 Cohen/Miyaji/Ono and substituting Z1=1 and Z2=1, 5M + 2S + 6add + 1times2, matching "9M + 2S" stated in 2005 Doche/Lange:
K<a,b,X1,X2>:=FieldOfFractions(PolynomialRing(Rationals(),4));
R<Y1,Y2>:=PolynomialRing(K,2);
Z1:=1; Z2:=1;
S:=quo<R|Y1^2*Z1-X1^3-a*X1*Z1^2-b*Z1^3,Y2^2*Z2-X2^3-a*X2*Z2^2-b*Z2^3>;
x1:=X1/Z1; y1:=Y1/Z1;
x2:=X2/Z2; y2:=Y2/Z2;
lambda:=(y2-y1)/(x2-x1);
x3:=lambda^2-x1-x2; y3:=lambda*(x1-x3)-y1;
// here are the formulas:
u:=Y2-Y1;
uu:=u^2;
v:=X2-X1;
vv:=v^2;
vvv:=v*vv;
R:=vv*X1;
A:=uu-vvv-2*R;
X3:=v*A;
Y3:=u*(R-A)-vvv*Y1;
Z3:=vvv;
S!(x3-X3/Z3); S!(y3-Y3/Z3);
Projective doubling (5M+6S+1D+7add+3times2+1times3) matches affine doubling. S,M counts stated in the literature: 7M+5S in 1998 Cohen/Miyaji/Ono. 7M+5S in 2005 Doche/Lange. 6M+6S in 2007 Bernstein/Lange.
1998 Cohen/Miyaji/Ono, formula (4):
K<a,b,X1,Y1>:=FieldOfFractions(PolynomialRing(Rationals(),4));
R<Z1>:=PolynomialRing(K,1);
S:=quo<R|Y1^2*Z1-X1^3-a*X1*Z1^2-b*Z1^3>;
X2:=X1; Y2:=Y1; Z2:=Z1;
x1:=X1/Z1; y1:=Y1/Z1;
S!(y1^2-x1^3-a*x1-b);
x2:=X2/Z2; y2:=Y2/Z2;
S!(y2^2-x2^3-a*x2-b);
lambda:=(3*x1^2+a)/(2*y1);
x3:=lambda^2-x1-x2; y3:=lambda*(x1-x3)-y1;
S!(y3^2-x3^3-a*x3-b);
// here are the formulas:
w:=a*Z1^2+3*X1^2;
s:=Y1*Z1;
B:=X1*Y1*s;
h:=w^2-8*B;
X3:=2*h*s;
Y3:=w*(4*B-h)-8*Y1^2*s^2;
Z3:=8*s^3;
S!(x3-X3/Z3); S!(y3-Y3/Z3);
Eliminating common subexpressions from 1998 Cohen/Miyaji/Ono,
6M + 5S + 1D + 4add + 1times2 + 1times3 + 1times4 + 3times8:
K<a,b,X1,Y1>:=FieldOfFractions(PolynomialRing(Rationals(),4));
R<Z1>:=PolynomialRing(K,1);
S:=quo<R|Y1^2*Z1-X1^3-a*X1*Z1^2-b*Z1^3>;
X2:=X1; Y2:=Y1; Z2:=Z1;
x1:=X1/Z1; y1:=Y1/Z1;
S!(y1^2-x1^3-a*x1-b);
x2:=X2/Z2; y2:=Y2/Z2;
S!(y2^2-x2^3-a*x2-b);
lambda:=(3*x1^2+a)/(2*y1);
x3:=lambda^2-x1-x2; y3:=lambda*(x1-x3)-y1;
S!(y3^2-x3^3-a*x3-b);
// here are the formulas:
w:=a*Z1^2+3*X1^2;
s:=Y1*Z1;
ss:=s^2;
sss:=s*ss;
R:=Y1*s;
B:=X1*R;
h:=w^2-8*B;
X3:=2*h*s;
Y3:=w*(4*B-h)-8*R^2;
Z3:=8*sss;
S!(x3-X3/Z3); S!(y3-Y3/Z3);
2007 Bernstein/Lange,
5M + 6S + 1D + 7add + 3times2 + 1times3:
K<a,b,X1,Y1>:=FieldOfFractions(PolynomialRing(Rationals(),4));
R<Z1>:=PolynomialRing(K,1);
S:=quo<R|Y1^2*Z1-X1^3-a*X1*Z1^2-b*Z1^3>;
X2:=X1; Y2:=Y1; Z2:=Z1;
x1:=X1/Z1; y1:=Y1/Z1;
S!(y1^2-x1^3-a*x1-b);
x2:=X2/Z2; y2:=Y2/Z2;
S!(y2^2-x2^3-a*x2-b);
lambda:=(3*x1^2+a)/(2*y1);
x3:=lambda^2-x1-x2; y3:=lambda*(x1-x3)-y1;
S!(y3^2-x3^3-a*x3-b);
// here are the formulas:
XX:=X1^2;
ZZ:=Z1^2;
w:=a*ZZ+3*XX;
s:=2*Y1*Z1;
ss:=s^2;
sss:=s*ss;
R:=Y1*s;
RR:=R^2;
B:=(X1+R)^2-XX-RR;
h:=w^2-2*B;
X3:=h*s;
Y3:=w*(B-h)-2*RR;
Z3:=sss;
S!(x3-X3/Z3); S!(y3-Y3/Z3);
Projective doubling for a=-3 (7M+3S+5add+4times2+1times3) matches affine doubling. Multiplication counts stated in the literature: 10 in 1986 Chudnovsky/Chudnovsky. 10 in 2004 Hankerson/Menezes/Vanstone, page 92. 10 in 2007 Bernstein/Lange.
S,M counts stated in the literature: 7M+3S in 2004 Hankerson/Menezes/Vanstone, page 92. 7M+3S in 2007 Bernstein/Lange.
Tweaking the above formulas, 7M + 3S + 5add + 4times2 + 1times3 in the special case a=-3:
K<b,X1,Y1>:=FieldOfFractions(PolynomialRing(Rationals(),3));
a:=-3;
R<Z1>:=PolynomialRing(K,1);
S:=quo<R|Y1^2*Z1-X1^3-a*X1*Z1^2-b*Z1^3>;
X2:=X1; Y2:=Y1; Z2:=Z1;
x1:=X1/Z1; y1:=Y1/Z1;
S!(y1^2-x1^3-a*x1-b);
x2:=X2/Z2; y2:=Y2/Z2;
S!(y2^2-x2^3-a*x2-b);
lambda:=(3*x1^2+a)/(2*y1);
x3:=lambda^2-x1-x2; y3:=lambda*(x1-x3)-y1;
S!(y3^2-x3^3-a*x3-b);
// here are the formulas:
w:=3*(X1-Z1)*(X1+Z1);
s:=2*Y1*Z1;
ss:=s^2;
sss:=s*ss;
R:=Y1*s;
RR:=R^2;
B:=2*X1*R;
h:=w^2-2*B;
X3:=h*s;
Y3:=w*(B-h)-2*RR;
Z3:=sss;
S!(x3-X3/Z3); S!(y3-Y3/Z3);
Projective doubling with Z1=1. 2007 Bernstein/Lange, 3M + 5S + 7add + 4times2 + 1times3 + 1times4:
K<a,b,X1>:=FieldOfFractions(PolynomialRing(Rationals(),3));
R<Y1>:=PolynomialRing(K,1);
Z1:=1;
S:=quo<R|Y1^2*Z1-X1^3-a*X1*Z1^2-b*Z1^3>;
X2:=X1; Y2:=Y1; Z2:=Z1;
x1:=X1/Z1; y1:=Y1/Z1;
S!(y1^2-x1^3-a*x1-b);
x2:=X2/Z2; y2:=Y2/Z2;
S!(y2^2-x2^3-a*x2-b);
lambda:=(3*x1^2+a)/(2*y1);
x3:=lambda^2-x1-x2; y3:=lambda*(x1-x3)-y1;
S!(y3^2-x3^3-a*x3-b);
// here are the formulas:
XX:=X1^2;
w:=a+3*XX;
Y1Y1:=Y1^2;
R:=2*Y1Y1;
sss:=4*Y1*R;
RR:=R^2;
B:=(X1+R)^2-XX-RR;
h:=w^2-2*B;
X3:=2*h*Y1;
Y3:=w*(B-h)-2*RR;
Z3:=sss;
S!(x3-X3/Z3); S!(y3-Y3/Z3);
Projective unified addition (11M+6S+1D+10add+4times2+1times4) matches affine doubling. 2002 Brier Joye, page 339, 12M + 5S + 1D + 7add + 3times2, strongly unified:
K<a,b,X1,Y1>:=FieldOfFractions(PolynomialRing(Rationals(),4));
R<Z1>:=PolynomialRing(K,1);
SS:=quo<R|Y1^2*Z1-X1^3-a*X1*Z1^2-b*Z1^3>;
X2:=X1; Y2:=Y1; Z2:=Z1;
x1:=X1/Z1; y1:=Y1/Z1;
SS!(y1^2-x1^3-a*x1-b);
x2:=X2/Z2; y2:=Y2/Z2;
SS!(y2^2-x2^3-a*x2-b);
lambda:=(3*x1^2+a)/(2*y1);
x3:=lambda^2-x1-x2; y3:=lambda*(x1-x3)-y1;
SS!(y3^2-x3^3-a*x3-b);
// here are the formulas:
U1:=X1*Z2;
U2:=X2*Z1;
S1:=Y1*Z2;
S2:=Y2*Z1;
Z:=Z1*Z2;
T:=U1+U2;
M:=S1+S2;
R:=T^2-U1*U2+a*Z^2;
F:=Z*M;
L:=M*F;
G:=T*L;
W:=R^2-G;
X3:=2*F*W;
Y3:=R*(G-2*W)-L^2;
Z3:=2*F*F^2;
SS!(x3-X3/Z3); SS!(y3-Y3/Z3);
2007 Bernstein/Lange, 11M + 6S + 1D + 10add + 4times2 + 1times4, strongly unified:
K<a,b,X1,Y1>:=FieldOfFractions(PolynomialRing(Rationals(),4));
R<Z1>:=PolynomialRing(K,1);
SS:=quo<R|Y1^2*Z1-X1^3-a*X1*Z1^2-b*Z1^3>;
X2:=X1; Y2:=Y1; Z2:=Z1;
x1:=X1/Z1; y1:=Y1/Z1;
SS!(y1^2-x1^3-a*x1-b);
x2:=X2/Z2; y2:=Y2/Z2;
SS!(y2^2-x2^3-a*x2-b);
lambda:=(3*x1^2+a)/(2*y1);
x3:=lambda^2-x1-x2; y3:=lambda*(x1-x3)-y1;
SS!(y3^2-x3^3-a*x3-b);
// here are the formulas:
U1:=X1*Z2;
U2:=X2*Z1;
S1:=Y1*Z2;
S2:=Y2*Z1;
Z:=Z1*Z2;
T:=U1+U2;
TT:=T^2;
M:=S1+S2;
R:=TT-U1*U2+a*Z^2;
F:=Z*M;
L:=M*F;
LL:=L^2;
G:=(T+L)^2-TT-LL;
W:=2*R^2-G;
X3:=2*F*W;
Y3:=R*(G-2*W)-2*LL;
Z3:=4*F*F^2;
SS!(x3-X3/Z3); SS!(y3-Y3/Z3);
Projective unified addition for a=-1 (13M+3S+8add+3times2) matches affine doubling. 2002 Brier Joye, page 340, 13M + 3S + 8add + 3times2 in the special case a = -1, strongly unified:
K<b,X1,Y1>:=FieldOfFractions(PolynomialRing(Rationals(),3));
a:=-1;
R<Z1>:=PolynomialRing(K,1);
SS:=quo<R|Y1^2*Z1-X1^3-a*X1*Z1^2-b*Z1^3>;
X2:=X1; Y2:=Y1; Z2:=Z1;
x1:=X1/Z1; y1:=Y1/Z1;
SS!(y1^2-x1^3-a*x1-b);
x2:=X2/Z2; y2:=Y2/Z2;
SS!(y2^2-x2^3-a*x2-b);
lambda:=(3*x1^2+a)/(2*y1);
x3:=lambda^2-x1-x2; y3:=lambda*(x1-x3)-y1;
SS!(y3^2-x3^3-a*x3-b);
// here are the formulas:
U1:=X1*Z2;
U2:=X2*Z1;
S1:=Y1*Z2;
S2:=Y2*Z1;
Z:=Z1*Z2;
T:=U1+U2;
M:=S1+S2;
R:=(T-Z)*(T+Z)-U1*U2;
F:=Z*M;
L:=M*F;
G:=T*L;
W:=R^2-G;
X3:=2*F*W;
Y3:=R*(G-2*W)-L^2;
Z3:=2*F*F^2;
SS!(x3-X3/Z3); SS!(y3-Y3/Z3);