On 5/15/14, Robert Ransom <[email protected]> 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 _______________________________________________ Curves mailing list [email protected] https://moderncrypto.org/mailman/listinfo/curves
