Explicit-Formulas Database

Doubling-oriented Doche/Icart/Kohel curves

An elliptic curve in doubling-oriented Doche/Icart/Kohel form is a curve of the form y^2 = x^3 + ax^2 + 16ax, where a(a-64) is nonzero. The neutral element of the curve is the point at infinity.

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);