Re: [Cfrg] New names for draft-ladd-safecurves

[Mike Hamburg <[e-mail]>]

On Jan 20, 2014, at 8:25 PM, Robert Ransom <[e-mail]> wrote:

> On 1/20/14, Mike Hamburg <[e-mail]> wrote:
> 
>> I suppose in that case we should be using curves with a small A or (A-2)/4
>> in Montgomery form instead of small d in Edwards form, because you need to
>> multiply by A more often: Edwards representations are probably fastest with
>> Niels+Extended coordinates at that size so they almost never multiply by d.
> 
> The Montgomery-form ladder is as efficient for small-integer
> Edwards-form d as it is for small-integer Montgomery-form parameter
> ((A-2)/4 or (A+2)/4).
> 
> 
> Robert Ransom

So it is.  Do you have a reference for that, BTW?  I derived it as:

x' = (x^2-z^2)^2
z' = 4xz(x^2 + Axz + z^2)

These are typically computed from (x+z)^2 and (x-z)^2, with 4xz being the difference between the two.

Substituting A = 2(1+d)/(1-d) = 4/(1-d)-2, we have

z' = 4xz(x^2 - 2xz + z^2 + 4xz/(1-d))

Scaling both x' and z' by (1-d) gives

x' = (x+z)^2 (x-z)^2 (1-d)
z' = 4xz(4xz + (1-d)(x-z)^2)

requiring the same 2 bigmuls, one smallmul and one add that the standard formula requires.

-- Mike