Pippenger Algorithm for Multi-Scalar Multiplication (MSM)

problem:

compute multiple scalar multiplication of ECC

\(S=k_i\cdot P_i\)

step 1:

decompose each scalar

step 2:

gather the decomposed scalars that has the same base together

step 3:

compute the gathered scalars addition using bucket method.

A very good explanation of the algorithm here

more readings here

Leave a Reply

Your email address will not be published. Required fields are marked *