Doubling-oriented Doche/Icart/Kohel coordinates represent an affine point (x,y) on a doubling-oriented Doche/Icart/Kohel-form elliptic curve y^2 = x^3 + ax^2 + 16ax as (X:Y:Z:ZZ) satisfying Y^2 = ZX^3 + aZ^2X^2 + 16aZ^3X and ZZ = Z^2. Here (X:Y:Z:ZZ) = (sX:s^2 Y:sZ:s^2 ZZ) for all nonzero s.
Speed records:
The following commands for the Magma computer-algebra system check various addition formulas for doubling-oriented Doche/Icart/Kohel coordinates.
Doubling-oriented Doche/Icart/Kohel scaling.
K<a,X1,Y1>:=FieldOfFractions(PolynomialRing(Rationals(),3));
R<Z1>:=PolynomialRing(K,1);
S:=quo<R|Y1^2-Z1*X1^3-a*Z1^2*X1^2-16*a*Z1^3*X1>;
// here are the formulas:
A:=1/Z1;
X2:=X1*A;
Y2:=Y1*A^2;
Z2:=1;
// check:
x1:=X1/Z1; y1:=Y1/Z1^2;
S!(y1^2-x1^3-a*x1^2-16*a*x1);
x2:=X2/Z2; y2:=Y2/Z2^2;
S!(y2^2-x2^3-a*x2^2-16*a*x2);
S!(Z2-1);
S!(x2-x1); S!(y2-y1);
Doubling-oriented Doche/Icart/Kohel addition (12M+5S+1D+10add+4times2) matches traditional addition. S,M counts stated in the literature: 12M+5S in 2007 Bernstein/Lange.
2006 Doche/Icart/Kohel, page 197, middle display, Z2 set to 1, affine only:
K<a,x1,x2>:=FieldOfFractions(PolynomialRing(Rationals(),3));
R<y1,y2>:=PolynomialRing(K,2);
S:=quo<R|y1^2-x1^3-a*x1^2-16*a*x1,y2^2-x2^3-a*x2^2-16*a*x2>;
X1:=x1; Y1:=y1; Z1:=1;
X2:=x2; Y2:=y2; Z2:=1;
// here are the formulas:
A:=Y1-Y2;
B:=X1-X2;
C:=B;
Z3:=C^2;
D:=X1*Z3;
E:=A^2;
F:=X2*B*C;
X3:=E-a*Z3-D-F;
G:=Z3^2;
H:=A*C;
Y3:=H*(D-X3)-Y1*G;
// back to affine:
x3:=X3/Z3; y3:=Y3/Z3^2;
S!(y3^2-x3^3-a*x3^2-16*a*x3);
// versus traditional affine formulas:
lambda:=(y2-y1)/(x2-x1);
r3:=lambda^2-a-x1-x2; s3:=lambda*(x1-r3)-y1;
// check the answer:
S!(x3-r3); S!(y3-s3);
Simplified, projectified:
K<a,X1,Y1,X2,Y2>:=FieldOfFractions(PolynomialRing(Rationals(),5));
R<Z1,Z2>:=PolynomialRing(K,2);
S:=quo<R|Y1^2-Z1*X1^3-a*Z1^2*X1^2-16*a*Z1^3*X1,Y2^2-Z2*X2^3-a*Z2^2*X2^2-16*a*Z2^3*X2>;
x1:=X1/Z1; y1:=Y1/Z1^2;
S!(y1^2-x1^3-a*x1^2-16*a*x1);
x2:=X2/Z2; y2:=Y2/Z2^2;
S!(y2^2-x2^3-a*x2^2-16*a*x2);
// here are the formulas:
A:=Y1/Z1^2-Y2/Z2^2;
B:=(X1/Z1)-(X2/Z2);
D:=(X1/Z1)*B^2;
X3:=A^2-a*B^2-D-(X2/Z2)*B^2;
Y3:=A*B*(D-X3)-(Y1/Z1^2)*B^4;
Z3:=B^2;
// back to affine:
x3:=X3/Z3; y3:=Y3/Z3^2;
S!(y3^2-x3^3-a*x3^2-16*a*x3);
// versus traditional affine formulas:
lambda:=(y2-y1)/(x2-x1);
r3:=lambda^2-a-x1-x2; s3:=lambda*(x1-r3)-y1;
// check the answer:
S!(x3-r3); S!(y3-s3);
Denominators cleared:
K<a,X1,Y1,X2,Y2>:=FieldOfFractions(PolynomialRing(Rationals(),5));
R<Z1,Z2>:=PolynomialRing(K,2);
S:=quo<R|Y1^2-Z1*X1^3-a*Z1^2*X1^2-16*a*Z1^3*X1,Y2^2-Z2*X2^3-a*Z2^2*X2^2-16*a*Z2^3*X2>;
x1:=X1/Z1; y1:=Y1/Z1^2;
S!(y1^2-x1^3-a*x1^2-16*a*x1);
x2:=X2/Z2; y2:=Y2/Z2^2;
S!(y2^2-x2^3-a*x2^2-16*a*x2);
// here are the formulas:
A:=Y1*Z2^2-Y2*Z1^2;
B:=X1*Z2-X2*Z1;
D:=Z1*Z2^2*B^2*X1;
U:=A^2-a*B^2*Z1^2*Z2^2-D-X2*B^2*Z1^2*Z2;
X3:=U;
Y3:=Z1*Z2*A*B*(D-U)-Z1^2*Z2^4*Y1*B^4;
Z3:=Z1^2*Z2^2*B^2;
// back to affine:
x3:=X3/Z3; y3:=Y3/Z3^2;
S!(y3^2-x3^3-a*x3^2-16*a*x3);
// versus traditional affine formulas:
lambda:=(y2-y1)/(x2-x1);
r3:=lambda^2-a-x1-x2; s3:=lambda*(x1-r3)-y1;
// check the answer:
S!(x3-r3); S!(y3-s3);
Common subexpressions eliminated,
2007 Bernstein/Lange,
12M+5S+1D+10add+4times2:
K<a,X1,Y1,X2,Y2>:=FieldOfFractions(PolynomialRing(Rationals(),5));
R<Z1,Z2>:=PolynomialRing(K,2);
S:=quo<R|Y1^2-Z1*X1^3-a*Z1^2*X1^2-16*a*Z1^3*X1,Y2^2-Z2*X2^3-a*Z2^2*X2^2-16*a*Z2^3*X2>;
x1:=X1/Z1; y1:=Y1/Z1^2;
S!(y1^2-x1^3-a*x1^2-16*a*x1);
x2:=X2/Z2; y2:=Y2/Z2^2;
S!(y2^2-x2^3-a*x2^2-16*a*x2);
// here are the formulas:
// already provided as part of input:
Z1Z1:=Z1^2;
Z2Z2:=Z2^2;
// uncached:
A:=Y1*Z2Z2-Y2*Z1Z1;
AA:=A^2;
X2Z1:=X2*Z1;
B:=X1*Z2-X2Z1;
C:=B*Z2;
E:=C*Z1;
EE:=E^2;
F:=E*C;
D:=F*X1;
U:=AA-a*EE-D-X2Z1*E*B;
X3:=2*U;
Y3:=2*((E+A)^2-EE-AA)*(D-U)-Y1*(2*F)^2;
Z3:=2*EE;
Z3Z3:=Z3^2;
// back to affine:
Z3Z3-Z3^2;
x3:=X3/Z3; y3:=Y3/Z3^2;
S!(y3^2-x3^3-a*x3^2-16*a*x3);
// versus traditional affine formulas:
lambda:=(y2-y1)/(x2-x1);
r3:=lambda^2-a-x1-x2; s3:=lambda*(x1-r3)-y1;
// check the answer:
S!(x3-r3); S!(y3-s3);
Doubling-oriented Doche/Icart/Kohel mixed addition (8M+4S+1D+10add+3times2) matches traditional addition. S,M,D counts stated in the literature: 9M+3S+1D in 2006 Doche/Icart/Kohel ("9M+3S if a multiplication by u is negligible"). 8M+4S+1D in 2007 Bernstein/Lange.
2006 Doche/Icart/Kohel, page 197, middle display, roles of 1 and 2 reversed, 9M+3S+1D+7add:
K<a,X1,Y1,X2>:=FieldOfFractions(PolynomialRing(Rationals(),4));
R<Z1,Y2>:=PolynomialRing(K,2);
Z2:=1;
S:=quo<R|Y1^2-Z1*X1^3-a*Z1^2*X1^2-16*a*Z1^3*X1,Y2^2-Z2*X2^3-a*Z2^2*X2^2-16*a*Z2^3*X2>;
// here are the formulas:
// already provided as part of input:
Z1Z1:=Z1^2;
// uncached:
A:=Y2*Z1Z1-Y1;
B:=X2*Z1-X1;
C:=B*Z1;
Z3:=C^2;
D:=X2*Z3;
E:=A^2;
F:=X1*B*C;
X3:=E-a*Z3-D-F;
G:=Z3^2;
H:=A*C;
Y3:=H*(D-X3)-Y2*G;
Z3Z3:=G;
// back to affine:
Z3Z3-Z3^2;
x3:=X3/Z3; y3:=Y3/Z3^2;
S!(y3^2-x3^3-a*x3^2-16*a*x3);
// versus traditional affine formulas:
x1:=X1/Z1; y1:=Y1/Z1^2;
x2:=X2/Z2; y2:=Y2/Z2^2;
lambda:=(y2-y1)/(x2-x1);
r3:=lambda^2-a-x1-x2; s3:=lambda*(x1-r3)-y1;
// check the answer:
S!(x3-r3); S!(y3-s3);
2007 Bernstein/Lange,
8M+4S+1D+10add+3times2:
K<a,X1,Y1,X2>:=FieldOfFractions(PolynomialRing(Rationals(),4));
R<Z1,Y2>:=PolynomialRing(K,2);
Z2:=1;
S:=quo<R|Y1^2-Z1*X1^3-a*Z1^2*X1^2-16*a*Z1^3*X1,Y2^2-Z2*X2^3-a*Z2^2*X2^2-16*a*Z2^3*X2>;
// here are the formulas:
// already provided as part of input:
Z1Z1:=Z1^2;
// uncached:
A:=Y2*Z1Z1-Y1;
AA:=A^2;
B:=X2*Z1-X1;
C:=B*Z1;
CC:=C^2;
D:=2*X2*CC;
F:=X1*B*C;
Z3:=2*CC;
Z3Z3:=Z3^2;
X3:=2*(AA-F)-a*Z3-D;
Y3:=((A+C)^2-AA-CC)*(D-X3)-Y2*Z3Z3;
// back to affine:
Z3Z3-Z3^2;
x3:=X3/Z3; y3:=Y3/Z3^2;
S!(y3^2-x3^3-a*x3^2-16*a*x3);
// versus traditional affine formulas:
x1:=X1/Z1; y1:=Y1/Z1^2;
x2:=X2/Z2; y2:=Y2/Z2^2;
lambda:=(y2-y1)/(x2-x1);
r3:=lambda^2-a-x1-x2; s3:=lambda*(x1-r3)-y1;
// check the answer:
S!(x3-r3); S!(y3-s3);
Doubling-oriented Doche/Icart/Kohel addition with Z1=1 and Z2=1 (4M + 4S + 1D + 10add + 3times2) matches traditional addition.
K<a,X1,Y1,X2>:=FieldOfFractions(PolynomialRing(Rationals(),4));
R<Z1,Y2>:=PolynomialRing(K,2);
Z1:=1; Z2:=1;
S:=quo<R|Y1^2-Z1*X1^3-a*Z1^2*X1^2-16*a*Z1^3*X1,Y2^2-Z2*X2^3-a*Z2^2*X2^2-16*a*Z2^3*X2>;
// here are the formulas:
A:=Y2-Y1;
AA:=A^2;
B:=X2-X1;
CC:=B^2;
D:=2*X2*CC;
F:=X1*CC;
Z3:=2*CC;
Z3Z3:=Z3^2;
X3:=2*(AA-F)-a*Z3-D;
Y3:=((A+B)^2-AA-CC)*(D-X3)-Y2*Z3Z3;
// back to affine:
Z3Z3-Z3^2;
x3:=X3/Z3; y3:=Y3/Z3^2;
S!(y3^2-x3^3-a*x3^2-16*a*x3);
// versus traditional affine formulas:
x1:=X1/Z1; y1:=Y1/Z1^2;
x2:=X2/Z2; y2:=Y2/Z2^2;
lambda:=(y2-y1)/(x2-x1);
r3:=lambda^2-a-x1-x2; s3:=lambda*(x1-r3)-y1;
// check the answer:
S!(x3-r3); S!(y3-s3);
Doubling-oriented Doche/Icart/Kohel doubling (2M+5S+2D+7add+3times2+1times8+1times64) matches traditional doubling. S,M,D counts stated in the literature: 3M+4S+2D in 2006 Doche/Icart/Kohel. 2M+5S+2D in 2007 Bernstein/Lange.
2006 Doche/Icart/Kohel, page 196, bottom display:
K<a,x1>:=FieldOfFractions(PolynomialRing(Rationals(),2));
R<y1>:=PolynomialRing(K,1);
S:=quo<R|y1^2-x1^3-a*x1^2-16*a*x1>;
x2:=x1; y2:=y1;
X1:=x1; Y1:=y1; Z1:=1;
X2:=x2; Y2:=y2; Z2:=1;
// here are the formulas:
A:=X1^2;
B:=X1^2-16*a*Z1^2;
YT:=Y1*B;
X3:=B^2;
Z3:=4*Y1^2;
C:=X1^2*a*Z1^2;
D:=Z3^2;
E:=a*(Z3-4*C);
Y3:=YT*(2*X3+E+256*C);
// back to affine:
x3:=X3/Z3; y3:=Y3/Z3^2;
S!(y3^2-x3^3-a*x3^2-16*a*x3);
// versus traditional affine formulas:
lambda:=(3*x1^2+2*a*x1+16*a)/(2*y1);
r3:=lambda^2-a-x1-x2; s3:=lambda*(x1-r3)-y1;
// check the answer:
S!(x3-r3); S!(y3-s3);
2006 Doche/Icart/Kohel, page 196, bottom display:
K<a,X1,Y1>:=FieldOfFractions(PolynomialRing(Rationals(),3));
R<Z1>:=PolynomialRing(K,1);
S:=quo<R|Y1^2-Z1*X1^3-a*Z1^2*X1^2-16*a*Z1^3*X1>;
X2:=X1; Y2:=Y1; Z2:=Z1;
// here are the formulas:
A:=X1^2;
B:=X1^2-16*a*Z1^2;
YT:=Y1*B;
X3:=B^2;
Z3:=4*Y1^2;
C:=X1^2*a*Z1^2;
D:=Z3^2;
E:=a*(Z3-4*C);
Y3:=YT*(2*X3+E+256*C);
// back to affine:
x3:=X3/Z3; y3:=Y3/Z3^2;
S!(y3^2-x3^3-a*x3^2-16*a*x3);
// versus traditional affine formulas:
x1:=X1/Z1; y1:=Y1/Z1^2;
x2:=X2/Z2; y2:=Y2/Z2^2;
lambda:=(3*x1^2+2*a*x1+16*a)/(2*y1);
r3:=lambda^2-a-x1-x2; s3:=lambda*(x1-r3)-y1;
// check the answer:
S!(x3-r3); S!(y3-s3);
2006 Doche/Icart/Kohel, page 196, bottom display,
common subexpressions eliminated,
3M+4S+2D+4add+3times2+1times4+1times32:
K<a,X1,Y1>:=FieldOfFractions(PolynomialRing(Rationals(),3));
R<Z1>:=PolynomialRing(K,1);
S:=quo<R|Y1^2-Z1*X1^3-a*Z1^2*X1^2-16*a*Z1^3*X1>;
X2:=X1; Y2:=Y1; Z2:=Z1;
// here are the formulas:
// already provided as part of input:
Z1Z1:=Z1^2;
// uncached:
A:=X1^2;
U:=4*a*Z1Z1;
B:=A-4*U;
C:=A*U;
Z3:=(2*Y1)^2;
X3:=B^2;
Y3:=Y1*B*(2*(X3+32*C)+a*(Z3-C));
Z3Z3:=Z3^2;
// back to affine:
x3:=X3/Z3; y3:=Y3/Z3^2;
S!(y3^2-x3^3-a*x3^2-16*a*x3);
// versus traditional affine formulas:
x1:=X1/Z1; y1:=Y1/Z1^2;
x2:=X2/Z2; y2:=Y2/Z2^2;
lambda:=(3*x1^2+2*a*x1+16*a)/(2*y1);
r3:=lambda^2-a-x1-x2; s3:=lambda*(x1-r3)-y1;
// check the answer:
S!(x3-r3); S!(y3-s3);
2007 Bernstein/Lange,
2M+5S+2D+7add+3times2+1times8+1times64:
K<a,X1,Y1>:=FieldOfFractions(PolynomialRing(Rationals(),3));
R<Z1>:=PolynomialRing(K,1);
S:=quo<R|Y1^2-Z1*X1^3-a*Z1^2*X1^2-16*a*Z1^3*X1>;
X2:=X1; Y2:=Y1; Z2:=Z1;
// here are the formulas:
// already provided as part of input:
Z1Z1:=Z1^2;
// uncached:
A:=X1^2;
U:=2*a*Z1Z1;
B:=A-8*U;
C:=A*U;
YY:=Y1^2;
YY2:=2*YY;
Z3:=2*YY2;
X3:=B^2;
V:=(Y1+B)^2-YY-X3;
Y3:=V*(X3+64*C+a*(YY2-C));
Z3Z3:=Z3^2;
// back to affine:
x3:=X3/Z3; y3:=Y3/Z3^2;
S!(y3^2-x3^3-a*x3^2-16*a*x3);
// versus traditional affine formulas:
x1:=X1/Z1; y1:=Y1/Z1^2;
x2:=X2/Z2; y2:=Y2/Z2^2;
lambda:=(3*x1^2+2*a*x1+16*a)/(2*y1);
r3:=lambda^2-a-x1-x2; s3:=lambda*(x1-r3)-y1;
// check the answer:
S!(x3-r3); S!(y3-s3);
Doubling-oriented Doche/Icart/Kohel doubling with Z1=1 (2M+5S+2D+7add+3times2+1times8+1times64) matches traditional doubling. S,M,D counts stated in the literature: 1M + 5S + 2D in 2007 Bernstein/Lange.
2007 Bernstein/Lange, 1M + 5S + 2D + 7add + 3times2 + 1times6 + 1times64:
K<a,X1>:=FieldOfFractions(PolynomialRing(Rationals(),2));
R<Y1>:=PolynomialRing(K,1);
Z1:=1;
S:=quo<R|Y1^2-X1^3-a*X1^2-16*a*X1>;
X2:=X1; Y2:=Y1; Z2:=Z1;
// here are the formulas:
// uncached:
A:=X1^2;
b:=2*a;
B:=A-8*b;
C:=b*A;
YY:=Y1^2;
YY2:=2*YY;
Z3:=2*YY2;
X3:=B^2;
V:=(Y1+B)^2-YY-X3;
Y3:=V*(X3+64*C+a*(YY2-C));
Z3Z3:=Z3^2;
// back to affine:
x3:=X3/Z3; y3:=Y3/Z3^2;
S!(y3^2-x3^3-a*x3^2-16*a*x3);
// versus traditional affine formulas:
x1:=X1/Z1; y1:=Y1/Z1^2;
x2:=X2/Z2; y2:=Y2/Z2^2;
lambda:=(3*x1^2+2*a*x1+16*a)/(2*y1);
r3:=lambda^2-a-x1-x2; s3:=lambda*(x1-r3)-y1;
// check the answer:
S!(x3-r3); S!(y3-s3);