Struct generic_ec::multiscalar::Pippenger

pub struct Pippenger;

Available on crate feature alloc only.

Pippenger algorithm

Outperforms Straus algorithm on $n \ge 50$. It has estimated performance:

$$\text{cost} = (4D + A)(log_{16} s - 1) + (n A + 30 A) log_{16} s$$

Algorithm

Inputs: list of $n$ points $P_1, \dots, P_n$ and scalars $s_1, \dots, s_n$. Each scalar is in radix 16 representation: $s_i = s_{i,0} + s_{i,1} 16^1 + \dots + s_{i,k-1} 16^{k-1}$ where $k = log_{16} s$, and $0 \le s_{i,j} < 16$

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

Steps:

Set $Q = \O$. For each $j \in [k-1, k-2, \dots, 1, 0]$:

1. Let $B$ be list of points indexed from $1$ to $15$, each element of which is initially set to $\O$, i.e. $B_1 = B_2 = \dots = B_{15} = \O$
2. Sort points $P_{1..n}$ into buckets $B$: for each $1 \le i \le n$, set $B_{s_{i,j}} := B_{s_{i,j}} + P_i$
3. Compute $S = 1 B_1 + 2 B_2 + \dots + 15 B_{15}$. To do this efficiently:
   1. Set $S’ := B_{15}$, $S := S’$
   2. Then, for each $m \in [14, 13, \dots, 1]$, do:
      Set $S’ := S’ + B_m$, and $S := S + S’$
4. Set $Q := 16 Q + S$

Output $Q$

How it works

Similarly to Straus algorithm, here we work with 2-dimention sum:

$$ \begin{aligned} s_1 P_1 &=&& s_{1,0} P_1 &&+&& 16^1 s_{1,1} P_1 &&+ \dots +&& 16^{k-1} s_{1,k-1} P_1 \\ + & && + && && + && && + \\ s_2 P_2 &=&& s_{2,0} P_2 &&+&& 16^1 s_{2,1} P_2 &&+ \dots +&& 16^{k-1} s_{2,k-1} P_2 \\ + & && + && && + && && + \\ \vdots & && \vdots && && \vdots && && \vdots \\ + & && + && && + && && + \\ s_n P_n &=&& s_{n,0} P_n &&+&& 16^1 s_{n,1} P_n &&+ \dots +&& 16^{k-1} s_{n,k-1} P_n \end{aligned} $$

We compute the sum column by column from right to left. The difference is how $s_{1,j} P_1 + s_{2,j} P_2 + \dots + s_{n,j} P_n$ is computed: Pippenger algorithm uses the buckets trick as described above.

Trait Implementations

impl<E: Curve> MultiscalarMul<E> for Pippenger

fn multiscalar_mul<S, P>( scalar_points: impl IntoIterator<Item = (S, P)> ) -> Point<E>

where S: AsRef<Scalar<E>>, P: AsRef<Point<E>>,

Performs multiscalar multiplication