Researches on hardware algorithms for arithmetic operations in finite fields.

点击翻译按钮获取中文摘要

We have investigated hardware algorithms for arithmetic operations in finite fields which play important roles in cryptosystems as well as in coding systems, and have obtained the following results.(1)We improved the hardware algorithm for division in finite field GF(2^m) based on the extended binary GCD method that we proposed previously, designed a circuit based on it, and evaluated the circuit by computer simulation as well as fabrication of a prototype LSI.(2)We developed a hardware algorithm for modular division/Montgomery multiplication, designed a circuit based on it, and evaluated the circuit by computer simulation. The modular division, i.e., division in finite field GF(p), is based on the extended binary GCD method. The two operations can be performed using a circuit whose amount of hardware is about the same as that of a modular divider based on the extended binary GCD method.(3)We developed a hardware algorithm for modular division/modular multiplication/Montgomery multipli … More cation, designed a circuit based on it, and evaluated the circuit by computer simulation. The modular division is based on the extended Euclid's algorithm. The three operations can be performed using a circuit whose amount of hardware is about the same as that of a modular divider based on the extended Euclid's algorithm.(4)We developed a hardware algorithm for computing multiplicative inverse in finite field GF(2^m) based on the extended Euclid's algorithm. This algorithm executes several steps of the extended Euclid's algorithm in one step using a look-up table. This algorithm is also suited for software implementation.(5)We developed a hardware algorithm for integer division which is used for modular reduction. In modular arithmetic, i.e., arithmetic in GF(p), modular reduction by p, i.e., the residue calculation of an integer divided by the modulus p, often appears. Since integer division is widely used, it is attractive to embed an integer divider based on the proposed algorithm in microprocessors for accelerating various computations. Less