Re: [Cfrg] Curve selection revisited

[Robert Ransom <[e-mail]>]

On 7/25/14, Robert Ransom <[e-mail]> wrote:

> Carries between limbs can be performed more efficiently than in
> curve25519-donna -- curve25519-donna goes to extra effort to keep
> limbs signed.  In the Montgomery ladder, this optimization does not
> add any extra carry steps, because the Montgomery-ladder formulas
> never perform more than two add/subtract operations between a
> multiply/square operation.  With Edwards-curve operations, this
> optimization may require an additional carry step in the doubling
> formula.

Er.  The ‘optimization’ I'm referring to is carrying in such a way
that the resulting limb values are always non-negative, in three
operations (shift, add, and bitwise and) rather than the seven (four
shifts, two adds, one subtract) needed to chop an extra bit off the
absolute value of each limb, and possibly producing negative limbs.


Dr. Bernstein wrote up his own explanation of how the performance of
unsaturated-limb arithmetic depends strongly on the exact values of s
and c on the curves list; see
<https://moderncrypto.org/mail-archive/curves/2014/000237.html>.  The
Curve41417 paper gives a more extensive treatment of how its
coordinate field allows even more optimization.


Robert Ransom