A Look-up Table based Binary GCD for Fast Modular Inversion

作者：Ishida Tsutomu^*; Nagase Tomoyuki; Yoshioka Yoshio

来源：Information-An International Interdisciplinary Journal, 2011, 14(8): 2901-2910.

• elliptic curves cryptosystem
• extended binary GCD method
• modular inversion algorithm

In both RSA and the elliptic curve cryptosystem (ECC), fast arithmetic operations between large integers are required over GF(p). Among all arithmetic operations on a finite field, the computational cost of divisions is the highest since it is necessary to calculate the modular inverse.
In this paper, we introduce a faster and more appropriate method using look-up table based on a modified version of the binary extended GCD algorithm. The new method can be implemented and running on simple operating environments such as embedded systems. The efficiency of our method has demonstrated by taking a comparison with the traditional word-based method.

• 出版日期2011-8