Ed25519 optimization that really only helps with embedded processors

Ed25519-optimization.txt

Awhile ago I found this pointless optimization for Ed25519 because it only saves a few
multiples. Also it doesn't help much unless you're on a 32bit or 8bit processor then it
kinda helps, but since you do 4x more doubles than adds it really isn't noticeable. Also
you can precalculate T*(2*-121665/121666) so it only helps on the initial 3 adds when
building 1*P, 2*P, 3*P, ... 8*P. If you store 60833*(Y-X), 60833*(Y+X), 121666*Z, 121665*T
then it's a little less work than storing Y-X, Y+X, 2*Z, k*T. Well this really only helps
if you are on an embedded processor and don't have the RAM to build the 1*P, 2*P, 3*P, ...
8*P lookup table. So it's not completely pointless.

This is from the Explicit-Formulas Database with d = -121665/121666
https://hyperelliptic.org/EFD/g1p/auto-twisted-extended-1.html#addition-add-2008-hwcd-3

A = (Y1-X1)*(Y2-X2)*60833
B = (Y1+X1)*(Y2+X2)*60833
C = T1*T2*121665
D = Z1*Z2*121666
E = B-A
F = D+C
G = D-C
H = B+A
X3 = E*F
Y3 = G*H
T3 = E*H
Z3 = F*G

------------------------------------
------------------------------------

Showing my work

k = 2*d

A = (Y1-X1)*(Y2-X2)
B = (Y1+X1)*(Y2+X2)
C = T1*k*T2
D = Z1*2*Z2
E = B-A
F = D-C
G = D+C
H = B+A
X3 = E*F
Y3 = G*H
T3 = E*H
Z3 = F*G

------------------------------------

d = -121665/121666

k = 2*d
k = 2*-121665/121666
k = -121665/60833


A = (Y1-X1)*(Y2-X2)
B = (Y1+X1)*(Y2+X2)
C = T1*-121665/60833*T2         **********
D = Z1*2*Z2
E = B-A
F = D-C
G = D+C
H = B+A
X3 = E*F
Y3 = G*H
T3 = E*H
Z3 = F*G

A = (Y1-X1)*(Y2-X2)
B = (Y1+X1)*(Y2+X2)
C = T1*T2                       **********
D = Z1*2*Z2
E = B-A
F = D-C*-121665/60833           **********
G = D+C*-121665/60833           **********
H = B+A
X3 = E*F
Y3 = G*H
T3 = E*H
Z3 = F*G

A = (Y1-X1)*(Y2-X2)
B = (Y1+X1)*(Y2+X2)
C = T1*T2
D = Z1*2*Z2
E = B-A
F = D+C*121665/60833            **********
G = D-C*121665/60833            **********
H = B+A
X3 = E*F
Y3 = G*H
T3 = E*H
Z3 = F*G

A = (Y1-X1)*(Y2-X2)
B = (Y1+X1)*(Y2+X2)
C = T1*T2
D = Z1*2*Z2
E = B-A
F = (D*60833+C*121665)/60833   **********
G = (D*60833-C*121665)/60833   **********
H = B+A
X3 = E*F
Y3 = G*H
T3 = E*H
Z3 = F*G

A = (Y1-X1)*(Y2-X2)
B = (Y1+X1)*(Y2+X2)
C = T1*T2*121665                **********
D = Z1*2*Z2*60833               **********
E = B-A
F = (D+C)/60833                 **********
G = (D-C)/60833                 **********
H = B+A
X3 = E*F
Y3 = G*H
T3 = E*H
Z3 = F*G

A = (Y1-X1)*(Y2-X2)
B = (Y1+X1)*(Y2+X2)
C = T1*T2*121665
D = Z1*Z2*121666                **********
E = B-A
F = (D+C)/60833
G = (D-C)/60833
H = B+A
X3 = E*F
Y3 = G*H
T3 = E*H
Z3 = F*G

A = (Y1-X1)*(Y2-X2)
B = (Y1+X1)*(Y2+X2)
C = T1*T2*121665
D = Z1*Z2*121666
E = B-A
F = D+C                         **********
G = D-C                         **********
H = B+A
X3 = E*F/60833                  **********
Y3 = G/60833*H                  **********
T3 = E*H
Z3 = F/60833*G/60833            **********

A = (Y1-X1)*(Y2-X2)
B = (Y1+X1)*(Y2+X2)
C = T1*T2*121665
D = Z1*Z2*121666
E = B-A
F = D+C
G = D-C
H = B+A
X3 = E*F/60833                  **********
Y3 = G*H/60833                  **********
T3 = E*H
Z3 = F*G/60833/60833            **********

x = X/Z
y = Y/Z
X*Y/Z = T

x = c/c * X/Z
y = c/c * Y/Z

X' = X*c
Y' = Y*c
Z' = Z*c

x = X'/Z'
y = Y'/Z'

X'*Y'/Z' = T'
X*c*Y*c/(Z*c) = T'
X*Y/Z*c = T'
T*c = T'
T' = T*c

Thus you can multiply by a constant to all X, Y, Z, T and it's still correct
X' = X*c
Y' = Y*c
Z' = Z*c
T' = T*c

A = (Y1-X1)*(Y2-X2)
B = (Y1+X1)*(Y2+X2)
C = T1*T2*121665
D = Z1*Z2*121666
E = B-A
F = D+C
G = D-C
H = B+A
X3 = E*F/60833       * 60833*60833  **********
Y3 = G*H/60833       * 60833*60833  **********
T3 = E*H             * 60833*60833  **********
Z3 = F*G/60833/60833 * 60833*60833  **********

A = (Y1-X1)*(Y2-X2)
B = (Y1+X1)*(Y2+X2)
C = T1*T2*121665
D = Z1*Z2*121666
E = B-A
F = D+C
G = D-C
H = B+A
X3 = E*F*60833                  **********
Y3 = G*H*60833                  **********
T3 = E*H*60833*60833            **********
Z3 = F*G                        **********

A = (Y1-X1)*(Y2-X2)
B = (Y1+X1)*(Y2+X2)
C = T1*T2*121665
D = Z1*Z2*121666
E = (B-A)*60833                 **********
F = D+C
G = D-C
H = (B+A)*60833                 **********
X3 = E*F                        **********
Y3 = G*H                        **********
T3 = E*H                        **********
Z3 = F*G                        **********

A = (Y1-X1)*(Y2-X2)*60833       **********
B = (Y1+X1)*(Y2+X2)*60833       **********
C = T1*T2*121665
D = Z1*Z2*121666
E = B-A                         **********
F = D+C
G = D-C
H = B+A                         **********
X3 = E*F
Y3 = G*H
T3 = E*H
Z3 = F*G