我々は、マルチスカラー倍計算における効率的な前計算方法を提案する。
マルチスカラー倍計算は、ECDSA署名スキームにおける署名検証等において
必要となる演算である。高速にマルチスカラー倍計算を行う方法として、
同時計算法を用いる方法がある。同時計算法は、実際の計算を行う評価ステージと、
評価ステージに必要となる値の前計算を行う前計算ステージとに分けられる。
同時計算法における評価ステージは、楕円加算を行う回数が少なくなるため、
高速に行うことができる。しかしながら、ウィンドウ幅を大きく取ると、
前計算を行う点の数が非常に多くなり、そのため、比較的計算量の大きな逆元演算
を行う回数が多くなる。その結果、前計算ステージに時間がかかってしまう。
提案法の前計算方法は、モンゴメリトリックを用いることにより、逆元演算の回数
を減少させ、高速化を図る。モンゴメリトリックを用いない前計算方法と比べ、
約3倍の高速化が図れる。
プログラムに戻る ．