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

[Andrey Jivsov <[e-mail]>]

On 01/11/2015 06:52 PM, Michael Hamburg wrote:
> Thanks for your analysis!  However, please note that with lazy extended homogeneous coordinates on a twisted Edwards curve with a=-1, the cost of an Edwards addition to an accumulator is 8M and not 10M+1S, and the cost of a doubling is still 3M+4S, perhaps with an additional 1M to convert from this form to a suitable one for the window table.
You are welcome. I would appreciate a pointer to the method.

>
> Furthermore, the multiplication by a constant in the Montgomery curve is not negligible, but neither is the cost of a constant-time lookup in the Edwards window table.

Right, I was ignoring additions and multiplication by a constant.

Assuming M/4 for a24 (e.g. 4-limb F(p) operations) and full M for d in 
t.Edwards (corresponding to the 37095705...283555 in 
draft-agl-cfrgcurve-00):

M: n*(5*M+4*S+M/4)+11*M + 245*S=1350*M + 1265*S
tE: 2^(w-2)*(10*M+S+M) + 2^(w-2)*(3*M+4*S) + 
w*(ceil(n/w)-1)*(3*M+4*S)+(ceil(n/w)-1)*(10*M+S+M)+11*M + 245*S=1423*M + 
1335*S

5.4%, 5.5% (M, S). Montgomery is better.

With small curve constants (A, d), M/4 for the multiplication by these 
constants:
M: currently optimal, same 1350*M + 1265*S
tE: 2^(w-2)*(10*M+S+M/4) + 2^(w-2)*(3*M+4*S) + 
w*(ceil(n/w)-1)*(3*M+4*S)+(ceil(n/w)-1)*(10*M+S+M/4)+11*M + 245*S=1380*M 
+ 1335*S

2.2%, 5.5%. Montgomery is better.