初めに 今回は、楕円曲線の数学的な性質を用いたスカラー倍算の高速化手法の一つ、GLV法(Gallant-Lambert-Vanstone)を紹介します。 GLV法は小さいマルチスカラー倍算を利用するので、まずそちらから解説しましょう。 マルチスカラー倍算 一般に、楕円曲線の点 P_1, \dots, P_n, 整数 a_1, \dots, a_n が与えられたときに Q=a_1 P_1 + \dots + a_n P_n を求める操作をマルチスカラー倍算 (MSM : multi-scalar multiplication)といいます。 zk-SNARKなどでは大きな n(数千~数万)に対するMSMが現れます。そのアルゴリズムはまたの機会に紹介するとして、ここでは n=2, つまり楕円曲線の点 P_1, P_2 と、整数 x_1, x_2 に対して Q=x_1 P_1 + x_2 P_2