[curves] Mutual-auth Ace (was Re: MQV)
Robert Ransom
rransom.8774 at gmail.com
Fri May 16 00:29:30 PDT 2014
On 5/15/14, Robert Ransom <rransom.8774 at gmail.com> wrote:
> A sane implementation of multi-exponentiation with N bases will take
> at most N/2 times the amount of time that a multi-exponentiation with
> 2 bases does, for small values of N. (With Straus's algorithm on a
> ‘large’ (smartphone-class) processor, the cost will increase
> non-linearly when the total table size approaches the processor's
> cache size, but it should stay linear for N up to 4.
Argh. The cost of table lookups and additions will be roughly linear
in N until the table overflows the cache; the point of using Straus's
algorithm is that the doublings are shared, so their total cost is
independent of N.
> With the
> Montgomery ladder on a constrained processor, the cost is roughly
> linear, but the final coordinate inversion is shared across the
> operation.)
Here the cost is closer to linear: N ladders with point recovery and
N-1 additions, then the inversion.
Robert Ransom
More information about the Curves
mailing list