Module multiscalar

Multiscalar multiplication

Let $s_{1, \dots, n}$ and $P_{1, \dots, n}$ be lists of scalars and points respectively. Multiscalar multiplication is computing point $Q$ such that:

$$Q = s_1 P_1 + \dots + s_n P_n$$

This module provides various algorithms for computing multiscalar multiplication efficiently.

Performance

Computing the sum naively, i.e. calculating each $s_i P_i$ separately and $\sum$-ing them, is inefficient even for small $n$. You can see that in the comparison below.

How to use it

In most cases, all you need is Scalar::multiscalar_mul which defaults to the most efficient available algorithm, similarly to Default.

Alternatively, if you need to use a specific algorithm, this module provides Straus and Dalek.

On Ed25519 curve, consider using Dalek multiscalar implementation.

Structs

Dalekcurve-ed25519 and alloc

Multiscalar implementation for Ed25519 curve

Default

Defaults to the most efficient multiscalar multiplication algorithm

Naive

Naive algorithm

Strausalloc

Straus algorithm

Traits

MultiscalarMul

Multiscalar multiplication algorithm