二進GCD法によるワードベース逆元計算の改良とその効率

摘要

楕円曲線暗号等 では，曲線上の2点の加算や倍点を求める計算を有限体上で行う．体上の四則演算のなかでは，道元の計算を求める必要があるため除算の演算コストが高い．道元を求める方法としては，拡張ユークリッド互除法2）や二進GCD法らがあり，それらについて改良されたワードベースの逆元計算アルゴリズムが提案されている．本論文では，その逆元計算アルゴリズムを事前計算されたテーブルを用いることにより，より高速計算を行うとともに，組み込みシステムのような低い演算環境でも動作できる手法を提案する．%On the elliptic curve cryptosystem (ECC), the addition of two points on the curve and the multiple computation of a point are calculated over the finite fields. Among all arithmetic operations on a field, the cost of operations for division is high since it is necessary to calculate the inversion. For calculating the inversion, there are traditional methods such as the extended Euclidian algorithm2' and the extended binary GCD method. And also a kind of ad vanced word-based inversion calculation algorithm is presented. Based on it, in this paper, by using pre-calculated table, we propose a kind of faster and more suitable method compared with the inversion calculation algorithm. This method can be implemented and running on simple operation environments such as embedded systems.