Inverted Edwards coordinates

Inverted Edwards coordinates represent an affine point (x,y) on an Edwards-form elliptic curve x^2 + y^2 = c^2(1 + dx^2y^2) as (X:Y:Z) satisfying (X^2 + Y^2)Z^2 = c^2(X^2Y^2 + dZ^4) with x = Z/X and y = Z/Y. Here (X:Y:Z) = (sX:sY:sZ) for all nonzero s. This representation does not cover the points (0,+-c) and (+-c,0).

Speed records:

Inverted-Edwards addition with c=1: 9M + 1S + 1D + 7add. Algorithm: 2007 Bernstein/Lange.
Inverted-Edwards strongly unified addition with c=1: 9M + 1S + 1D + 7add. Algorithm: 2007 Bernstein/Lange.
Inverted-Edwards mixed addition with c=1: 8M + 1S + 1D + 7add. Algorithm: 2007 Bernstein/Lange.
Inverted-Edwards addition with X2=1 with c=1: 8M + 1S + 1D + 4add. Algorithm: 2007 Bernstein/Lange.
Inverted-Edwards addition with Z1=1 and Z2=1 and c=1: 7M + 7add. Algorithm: 2007 Bernstein/Lange.
Inverted-Edwards doubling with c=1: 3M + 4S + 1D + 5add + 1times2. Algorithm: 2007 Bernstein/Lange.
Inverted-Edwards doubling with Z1=1: with c=1: 3M+3S+5add+1times2. Algorithm: 2007 Bernstein/Lange.
Inverted-Edwards tripling with c=1: 9M + 4S + 1D + 7add + 1times2 + 1times4. Algorithm: 2007 Bernstein/Lange.

Some speed records are different when S/M is small:

Inverted-Edwards tripling with c=1: 7M + 7S + 1D + 13add + 2times2 + 1times4. Algorithm: 2007 Bernstein/Lange.

The following commands for the Magma computer-algebra system check various addition formulas for inverted Edwards coordinates.

Inverted-Edwards scaling.

     K<c,d,X1,Y1>:=FieldOfFractions(PolynomialRing(Rationals(),4));
     e:=1-d*c^4;
     R<Z1>:=PolynomialRing(K,1);
     S:=quo<R|(X1^2+Y1^2)*Z1^2-c^2*(d*Z1^4+X1^2*Y1^2)>;
     // here are the formulas:
     A:=1/Z1;
     X2:=X1*A;
     Y2:=Y1*A;
     Z2:=1;
     // check:
     x1:=Z1/X1; y1:=Z1/Y1;
     S!(x1^2+y1^2-c^2*(1+d*x1^2*y1^2));
     x2:=Z2/X2; y2:=Z2/Y2;
     S!(x2^2+y2^2-c^2*(1+d*x2^2*y2^2));
     S!(Z2-1);
     S!(x2-x1); S!(y2-y1);

Inverted-Edwards addition (9M + 1S + 2C + 1D + 7add) matches traditional addition. 2007 Bernstein/Lange, 9M + 1S + 2C + 1D + 7add, strongly unified:

     K<c,d,X1,Y1,X2,Y2>:=FieldOfFractions(PolynomialRing(Rationals(),6));
     e:=1-d*c^4;
     R<Z1,Z2>:=PolynomialRing(K,2);
     S:=quo<R|(X1^2+Y1^2)*Z1^2-c^2*(d*Z1^4+X1^2*Y1^2),(X2^2+Y2^2)*Z2^2-c^2*(d*Z2^4+X2^2*Y2^2)>;
     x1:=Z1/X1; y1:=Z1/Y1;
     S!(x1^2+y1^2-c^2*(1+d*x1^2*y1^2));
     x2:=Z2/X2; y2:=Z2/Y2;
     S!(x2^2+y2^2-c^2*(1+d*x2^2*y2^2));
     x3:=(x1*y2+y1*x2)/(c*(1+d*x1*x2*y1*y2)); y3:=(y1*y2-x1*x2)/(c*(1-d*x1*x2*y1*y2));
     S!(x3^2+y3^2-c^2*(1+d*x3^2*y3^2));
     // here are the formulas:
     A:=Z1*Z2;
     B:=d*A^2;
     C:=X1*X2;
     D:=Y1*Y2;
     E:=C*D;
     H:=C-D;
     I:=(X1+Y1)*(X2+Y2)-C-D;
     X3:=c*(E+B)*H;
     Y3:=c*(E-B)*I;
     Z3:=A*H*I;
     S!(x3-Z3/X3); S!(y3-Z3/Y3);

Inverted-Edwards mixed addition (8M + 1S + 2C + 1D + 7add) matches traditional addition. 2007 Bernstein/Lange, 8M + 1S + 2C + 1D + 7add:

     K<c,d,X1,Y1,X2>:=FieldOfFractions(PolynomialRing(Rationals(),5));
     e:=1-d*c^4;
     R<Z1,Y2>:=PolynomialRing(K,2);
     Z2:=1;
     S:=quo<R|(X1^2+Y1^2)*Z1^2-c^2*(d*Z1^4+X1^2*Y1^2),(X2^2+Y2^2)*Z2^2-c^2*(d*Z2^4+X2^2*Y2^2)>;
     x1:=Z1/X1; y1:=Z1/Y1;
     S!(x1^2+y1^2-c^2*(1+d*x1^2*y1^2));
     x2:=Z2/X2; y2:=Z2/Y2;
     S!(x2^2+y2^2-c^2*(1+d*x2^2*y2^2));
     x3:=(x1*y2+y1*x2)/(c*(1+d*x1*x2*y1*y2)); y3:=(y1*y2-x1*x2)/(c*(1-d*x1*x2*y1*y2));
     S!(x3^2+y3^2-c^2*(1+d*x3^2*y3^2));
     // here are the formulas:
     A:=Z1;
     B:=d*A^2;
     C:=X1*X2;
     D:=Y1*Y2;
     E:=C*D;
     H:=C-D;
     I:=(X1+Y1)*(X2+Y2)-C-D;
     X3:=c*(E+B)*H;
     Y3:=c*(E-B)*I;
     Z3:=A*H*I;
     S!(x3-Z3/X3); S!(y3-Z3/Y3);

Inverted-Edwards addition with X2=1 (8M + 1S + 2C + 1D + 4add) matches traditional addition. 2007 Bernstein/Lange, 8M + 1S + 2C + 1D + 4add:

     K<c,d,X1,Y1,Y2>:=FieldOfFractions(PolynomialRing(Rationals(),5));
     e:=1-d*c^4;
     R<Z1,Z2>:=PolynomialRing(K,2);
     X2:=1;
     S:=quo<R|(X1^2+Y1^2)*Z1^2-c^2*(d*Z1^4+X1^2*Y1^2),(X2^2+Y2^2)*Z2^2-c^2*(d*Z2^4+X2^2*Y2^2)>;
     x1:=Z1/X1; y1:=Z1/Y1;
     S!(x1^2+y1^2-c^2*(1+d*x1^2*y1^2));
     x2:=Z2/X2; y2:=Z2/Y2;
     S!(x2^2+y2^2-c^2*(1+d*x2^2*y2^2));
     x3:=(x1*y2+y1*x2)/(c*(1+d*x1*x2*y1*y2)); y3:=(y1*y2-x1*x2)/(c*(1-d*x1*x2*y1*y2));
     S!(x3^2+y3^2-c^2*(1+d*x3^2*y3^2));
     // here are the formulas:
     A:=Z1*Z2;
     B:=d*A^2;
     D:=Y1*Y2;
     E:=X1*D;
     F:=E-B;
     G:=E+B;
     H:=X1-D;
     I:=X1*Y2+Y1;
     X3:=c*G*H;
     Y3:=c*F*I;
     Z3:=A*H*I;
     S!(x3-Z3/X3); S!(y3-Z3/Y3);

Inverted-Edwards addition with Z1=1 and Z2=1. 2007 Bernstein/Lange, 7M + 2C + 7add:

     K<c,d,X1,X2>:=FieldOfFractions(PolynomialRing(Rationals(),4));
     e:=1-d*c^4;
     R<Y1,Y2>:=PolynomialRing(K,2);
     Z1:=1; Z2:=1;
     S:=quo<R|(X1^2+Y1^2)*Z1^2-c^2*(d*Z1^4+X1^2*Y1^2),(X2^2+Y2^2)*Z2^2-c^2*(d*Z2^4+X2^2*Y2^2)>;
     x1:=Z1/X1; y1:=Z1/Y1;
     S!(x1^2+y1^2-c^2*(1+d*x1^2*y1^2));
     x2:=Z2/X2; y2:=Z2/Y2;
     S!(x2^2+y2^2-c^2*(1+d*x2^2*y2^2));
     x3:=(x1*y2+y1*x2)/(c*(1+d*x1*x2*y1*y2)); y3:=(y1*y2-x1*x2)/(c*(1-d*x1*x2*y1*y2));
     S!(x3^2+y3^2-c^2*(1+d*x3^2*y3^2));
     // here are the formulas:
     C:=X1*X2;
     D:=Y1*Y2;
     E:=C*D;
     H:=C-D;
     I:=(X1+Y1)*(X2+Y2)-C-D;
     X3:=c*(E+d)*H;
     Y3:=c*(E-d)*I;
     Z3:=H*I;
     S!(x3-Z3/X3); S!(y3-Z3/Y3);

Inverted-Edwards doubling (3M + 4S + 3C + 1D + 5add + 1times2) matches traditional doubling. 2007 Bernstein/Lange, 9M + 1S + 2C + 1D + 7add, strongly unified:

     K<c,d,X1,Y1>:=FieldOfFractions(PolynomialRing(Rationals(),4));
     e:=1-d*c^4;
     R<Z1>:=PolynomialRing(K,1);
     S:=quo<R|(X1^2+Y1^2)*Z1^2-c^2*(d*Z1^4+X1^2*Y1^2)>;
     x1:=Z1/X1; y1:=Z1/Y1;
     S!(x1^2+y1^2-c^2*(1+d*x1^2*y1^2));
     x2:=x1; y2:=y1;
     S!(x2^2+y2^2-c^2*(1+d*x2^2*y2^2));
     x3:=(x1*y2+y1*x2)/(c*(1+d*x1*x2*y1*y2)); y3:=(y1*y2-x1*x2)/(c*(1-d*x1*x2*y1*y2));
     S!(x3^2+y3^2-c^2*(1+d*x3^2*y3^2));
     X2:=X1; Y2:=Y1; Z2:=Z1;
     // here are the formulas:
     A:=Z1*Z2;
     B:=d*A^2;
     C:=X1*X2;
     D:=Y1*Y2;
     E:=C*D;
     H:=C-D;
     I:=(X1+Y1)*(X2+Y2)-C-D;
     X3:=c*(E+B)*H;
     Y3:=c*(E-B)*I;
     Z3:=A*H*I;
     S!(x3-Z3/X3); S!(y3-Z3/Y3);

2007 Bernstein/Lange, 3M + 4S + 3C + 1D + 5add + 1times2:

     K<c,d,X1,Y1>:=FieldOfFractions(PolynomialRing(Rationals(),4));
     e:=1-d*c^4;
     R<Z1>:=PolynomialRing(K,1);
     S:=quo<R|(X1^2+Y1^2)*Z1^2-c^2*(d*Z1^4+X1^2*Y1^2)>;
     x1:=Z1/X1; y1:=Z1/Y1;
     S!(x1^2+y1^2-c^2*(1+d*x1^2*y1^2));
     x2:=x1; y2:=y1;
     S!(x2^2+y2^2-c^2*(1+d*x2^2*y2^2));
     x3:=(x1*y2+y1*x2)/(c*(1+d*x1*x2*y1*y2)); y3:=(y1*y2-x1*x2)/(c*(1-d*x1*x2*y1*y2));
     S!(x3^2+y3^2-c^2*(1+d*x3^2*y3^2));
     X2:=X1; Y2:=Y1; Z2:=Z1;
     // here are the formulas:
     A:=X1^2;
     B:=Y1^2;
     C:=A+B;
     D:=A-B;
     E:=(X1+Y1)^2-C;
     Z3:=c*D*E;
     X3:=C*D;
     Y3:=E*(C-2*c*c*d*Z1^2);
     S!(x3-Z3/X3); S!(y3-Z3/Y3);

Inverted-Edwards doubling with Z1=1 (3M+3S+3C+5add+1times2) matches traditional doubling. 2007 Bernstein/Lange, 3M + 3S + 3C + 5add + 1times2:

     K<c,d,X1>:=FieldOfFractions(PolynomialRing(Rationals(),3));
     e:=1-d*c^4;
     Z1:=1; 
     R<Y1>:=PolynomialRing(K,1);
     S:=quo<R|(X1^2+Y1^2)*Z1^2-c^2*(d*Z1^4+X1^2*Y1^2)>;
     x1:=Z1/X1; y1:=Z1/Y1;
     S!(x1^2+y1^2-c^2*(1+d*x1^2*y1^2));
     x2:=x1; y2:=y1;
     S!(x2^2+y2^2-c^2*(1+d*x2^2*y2^2));
     x3:=(x1*y2+y1*x2)/(c*(1+d*x1*x2*y1*y2)); y3:=(y1*y2-x1*x2)/(c*(1-d*x1*x2*y1*y2));
     S!(x3^2+y3^2-c^2*(1+d*x3^2*y3^2));
     X2:=X1; Y2:=Y1; Z2:=Z1;
     // here are the formulas:
     A:=X1^2;
     B:=Y1^2;
     C:=A+B;
     D:=A-B;
     E:=(X1+Y1)^2-C;
     Z3:=c*D*E;
     X3:=C*D;
     Y3:=E*(C-2*c*c*d);
     S!(x3-Z3/X3); S!(y3-Z3/Y3);

Inverted-Edwards tripling (9M + 4S + 1C + 1D + 7add + 1times2 + 1times4) matches traditional tripling. 2007 Bernstein/Lange, 9M + 4S + 1C + 1D + 7add + 1times2 + 1times4:

     K<c,d,X1,Y1>:=FieldOfFractions(PolynomialRing(Rationals(),4));
     e:=1-d*c^4;
     R<Z1>:=PolynomialRing(K,1);
     S:=quo<R|(X1^2+Y1^2)*Z1^2-c^2*(d*Z1^4+X1^2*Y1^2)>;
     x1:=Z1/X1; y1:=Z1/Y1;
     S!(x1^2+y1^2-c^2*(1+d*x1^2*y1^2));
     x2:=(x1*y1+y1*x1)/(c*(1+d*x1*x1*y1*y1));
     y2:=(y1*y1-x1*x1)/(c*(1-d*x1*x1*y1*y1));
     S!(x2^2+y2^2-c^2*(1+d*x2^2*y2^2));
     x3:=(x1*y2+y1*x2)/(c*(1+d*x1*x2*y1*y2));
     y3:=(y1*y2-x1*x2)/(c*(1-d*x1*x2*y1*y2));
     S!(x3^2+y3^2-c^2*(1+d*x3^2*y3^2));
     // here are the formulas:
     XX:=X1^2;
     YY:=Y1^2;
     ZZ:=(c*Z1)^2;
     D:=XX+YY;
     DD:=D^2;
     E:=4*(D-d*ZZ);
     H:=2*D*(YY-XX);
     P:=DD-XX*E;
     Q:=DD-YY*E;
     X3:=(H+Q)*Q*X1;
     Y3:=(H-P)*P*Y1;
     Z3:=P*Q*Z1;
     S!(x3-Z3/X3); S!(y3-Z3/Y3);

2007 Bernstein/Lange, 7M + 7S + 1C^2 + 1D + 13add + 2times2 + 1times4:

     K<c,d,X1,Y1>:=FieldOfFractions(PolynomialRing(Rationals(),4));
     e:=1-d*c^4;
     R<Z1>:=PolynomialRing(K,1);
     S:=quo<R|(X1^2+Y1^2)*Z1^2-c^2*(d*Z1^4+X1^2*Y1^2)>;
     x1:=Z1/X1; y1:=Z1/Y1;
     S!(x1^2+y1^2-c^2*(1+d*x1^2*y1^2));
     x2:=(x1*y1+y1*x1)/(c*(1+d*x1*x1*y1*y1));
     y2:=(y1*y1-x1*x1)/(c*(1-d*x1*x1*y1*y1));
     S!(x2^2+y2^2-c^2*(1+d*x2^2*y2^2));
     x3:=(x1*y2+y1*x2)/(c*(1+d*x1*x2*y1*y2));
     y3:=(y1*y2-x1*x2)/(c*(1-d*x1*x2*y1*y2));
     S!(x3^2+y3^2-c^2*(1+d*x3^2*y3^2));
     // here are the formulas:
     XX:=X1^2;
     YY:=Y1^2;
     ZZ:=Z1^2;
     D:=XX+YY;
     DD:=D^2;
     E:=4*(D-d*c*c*ZZ);
     H:=2*D*(YY-XX);
     P:=DD-XX*E;
     Q:=DD-YY*E;
     QQ:=Q^2;
     X3:=(H+Q)*((Q+X1)^2-QQ-XX);
     Y3:=2*(H-P)*P*Y1;
     Z3:=P*((Q+Z1)^2-QQ-ZZ);
     S!(x3-Z3/X3); S!(y3-Z3/Y3);