Re: [Cfrg] On relative performance of Edwards v.s. Montgomery Curve25519, variable base

[Andrey Jivsov <[e-mail]>]

Counting multiplications (M) and squares (S) in F(p), ECC formulas use 
at least 5% more operations v.s. Montgomery.

The lowest non-Montgomery count is reached with twisted Edwards, signed 
window, w=5, which yields 6%/5.5% more M/S.

I pasted my notes below.

It's possible that my initial results in this thread are due to the 
difference in F(p) operations between the two implementations.

See also http://www.ietf.org/mail-archive/web/cfrg/current/msg05857.html

Thanks to Mike and Watson for pointers and comments.


-----------------------------------------------------------------
Montgomery method:
-----------------------------------------------------------------

 From http://hyperelliptic.org/EFD/g1p/auto-montgom-xz.html (8.2M for 
differential addition and doubling) with Z1=1: 5M+4S.

256*(5*M+4*S)=1275*M + 1020*S
Inverse: 11*M + 245*S

(also checked curve25519-donna-c64.c)

Total: 1285*M + 1265*S

-----------------------------------------------------------------
t.Edwards window method:
-----------------------------------------------------------------

Write the windows size as w and n-bit E(F(p)) curve (e.g. n=255). 
2^(w-1) signed elements need to be calculated.

The half of 2^(w-1) is filled with doubles, half with additions

2^(w-2) additions, 2^(w-2) doubles, z!=1

addition: 10M+1S
double: 3M+4S
from http://hyperelliptic.org/EFD/g1p/auto-twisted-projective.html

Window filling:
2^(w-2)*(10*M+S) + 2^(w-2)*(3*M+4*S)

For windowed scalar multiplication there are w(ceil(n/w)-1) doubles and 
ceil(255/w)-1 additions

w*(ceil(n/w)-1)*(3*M+4*S)+(ceil(n/w)-1)*(10*M+S)

The formula is 2^(w-2)*(10*M+S) + 2^(w-2)*(3*M+4*S) + 
w*(ceil(n/w)-1)*(3*M+4*S)+(ceil(n/w)-1)*(10*M+S)

w=3: 1622*M + 1102*S
w=4: 1438*M + 1091*S
w=5: 1354*M + 1090*S
w=6: 1384*M + 1130*S

Inverse: 11*M + 245*S

Total (w=5) with inverse:
1354*M + 1090*S +11*M + 245*S = 1365*M + 1335*S

So we have

Montgomery (M):     1285*M + 1265*S
t.Edwards w=5 (tE): 1365*M + 1335*S
( tE needs 6% more M, 5.5% more S )

Unifying S+M, this is:

for S=M cost:
M: 2550*M
tE: 2700*M

for S=0.625M cost:
M: 2075M
E: 2200M

Watson's estimate is:
Montgomery: 2491M
t.Edwards w=5: 2714M

-----------------------------------------------------------------
"Jacobian coordinates with a4=0 for short Weierstrass curves", window method
-----------------------------------------------------------------
http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html

doubling: 2M+5S
addition:  11M+5S

2^(w-2)*(11*M+5*S) + 2^(w-2)*(2*M+5*S) + 
w*(ceil(n/w)-1)*(2*M+5*S)+(ceil(n/w)-1)*(11*M+5*S) + 11*M + 245*S

w=5: 1165*M + 1825*S

for S=M cost
2990*M

for S=0.625M cost
2305*M

-----------------------------------------------------------------
variable curve size n, window method
-----------------------------------------------------------------

Hand-waive (extrapolate from Curve25519) the inverse as
0.95*n*S+0.05*n*M

Montgomery:
(n+1)*(5*M+4*S)+0.95*n*S+0.05*n*M

t.Edwards:
F=2^(w-2)*(10*M+S) + 2^(w-2)*(3*M+4*S) + 
w*(ceil(n/w)-1)*(3*M+4*S)+(ceil(n/w)-1)*(10*M+S)+ 0.95*n*S+0.05*n*M

n=384:
M: 1944*M + 1904*S
w=5:
tE: 2023*M + 2000*S
w=6:
tE: 1991*M + 2019*S

n=255, w=5  (compare to the actual, above):
M: 1292*M + 1266*S
tE: 1366*M + 1332*S

n=400:
M: 2025*M + 1984*S
w=5:
tE: 2099*M + 2079*S
w=6:
tE: 2076*M + 2110.*S
w=7:
tE: 2203*M + 2193*S

n=512:
M: 2590*M + 2538*S
w=5:
tE: 2679*M + 2668*S
w=6:
tE: 2613*M + 2691*S

-----------------------------------------------------------------
Comb method
-----------------------------------------------------------------
The method is described here: http://eprint.iacr.org/2005/222.pdf, but 
always add O:

precomp: (w-1)*ceil(n/w)(3M+4S) + ((2^w)-w-1)*(10M+1S)
mult: (ceil(n/w)-1)*(3M+4S+10M+1S)
inverse (n=255): 11*M + 245*S

total: (w-1)*ceil(n/w)*(3*M+4*S) + ((2^(w-1))-w-1)*(10*M+S) + 
(ceil(n/w)-1)*(3*M+4*S+10*M+S)+11*M + 245*S

n=255:
w=3:
1653*M + 1349*S
w=4:
1516*M + 1339*S
w=5:
1533*M + 1337*S
w=6:
1772*M + 1372*S