Straus' trickによるMSM
概要
MSM (multi-scalar multiplication)を計算するための効率的な方法
目的は$ x_0, \ldots, x_{r-1} \in Gと$ lビットの自然数$ n_0, \ldots, n_{r-1}に対し、$ x_0^{n_0} \cdots x_{r-1}^{n_{r-1}}を求めること。
手順
予め自然数$ 0 \le i < 2^rに対し、
$ g_i=\prod_{j=0}^{r-1} x_j^{i_j}
を計算しておく。ただし、$ i_jは$ iの$ j番目のビット( つまり$ x_jの項のある/ないで全てのパターンを計算しておく)。
$ y = 1とし、$ k = l -1から$ k = 0まで1ずつ減らしながら次のループを実行する。
1. $ y \leftarrow y^2
2. $ i \leftarrow \sum_{j = 0}^{r-1} n_{j, k} 2^j ($ n_{j, k} は$ n_jの$ k番目のビット)
3. $ y \leftarrow y g_i
イメージとしては、個別にscalar multiplicationを実行するのが「縦」の処理なら、これは「横」の処理。それによって$ y \leftarrow y^2の部分を共通化でき、効率化できる。ただし、$ rの冪乗の大きさの事前処理が必要になるので、$ rはそれほど大きくない値(例えば$ r = 2)にする必要がある。
参考文献