Researches on hardware algorithms for arithmetic operations in finite fields.

我们研究了有限域中算术运算的硬件算法，这些算法在密码系统和编码系统中起着重要的作用，并得到了以下结果。(1)基于先前提出的扩展二进制GCD方法，改进了有限域GF（2^m）除法的硬件算法，设计了基于该算法的电路，并通过计算机仿真和原型LSI的制作对该电路进行了评价。(2)提出了模块化除法/蒙哥马利乘法的硬件算法，设计了基于该算法的电路，并通过计算机仿真对电路进行了评价。模除法，即有限域GF(p)上的除法，是基于扩展二进制GCD方法的。这两种操作可以使用硬件数量与基于扩展二进制GCD方法的模块化分频器的硬件数量大致相同的电路来执行。(3)提出了模块化除法/模块化乘法/蒙哥马利乘法的硬件算法，并在此基础上设计了电路，并通过计算机仿真对电路进行了评价。模除法基于扩展欧几里得算法。这三个操作可以用一个电路来完成，这个电路的硬件数量与基于扩展欧几里得算法的模块化分法器的硬件数量大致相同。(4)在扩展欧几里得算法的基础上，提出了一种计算有限域GF（2^m）乘法逆的硬件算法。该算法使用查找表一步执行扩展欧几里得算法的几个步骤。该算法也适合于软件实现。(5)开发了一种用于模块化约简的整数除法硬件算法。在模算法中，即GF(p)中的算法，常出现p的模约简，即整数除以模p的余数计算。由于整数除法的广泛应用，因此在微处理器中嵌入基于该算法的整数除法器以加速各种计算是很有吸引力的。少

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