Explicit-Formulas Database

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

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

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

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