权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Researches on hardware algorithms for arithmetic operations in finite fields.

研究有限域算术运算的硬件算法。

基本信息

批准号：
14380142
负责人：
TAKAGI Naofumi
金额：
$ 9.28万
依托单位：
Nagoya University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (B)
财政年份：
2002
资助国家：
日本
起止时间：
2002 至 2004
项目状态：
已结题

项目摘要

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

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