Explicit-Formulas Database

Projective coordinates

Projective coordinates represent an affine point (x,y) on a Weierstrass-form elliptic curve y^2 = x^3 + ax + b as (X:Y:Z) satisfying Y^2 Z = X^3 + aXZ^2 + bZ^3. Here (X:Y:Z) = (sX:sY:sZ) for all nonzero s.

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