楕円曲線暗号のための数学6（GLV法と自己準同型写像）

初めに 今回は、楕円曲線の数学的な性質を用いたスカラー倍算の高速化手法の一つ、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