Redundant Radix-2r Number System for Accelerating Arithmetic Operations on the FPGAs
Redundant Radix-2r Number System for Accelerating Arithmetic Operations on the FPGAs
复制标题
用于加速 FPGA 算术运算的冗余 Radix-2r 数字系统
DOI：
10.1109/pdcat.2008.13
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
K. Nakano
中科院分区：
文献类型：
--
作者：
Kensuke Kawakami;K. Shigemoto;K. Nakano
本文的主要贡献是为FPGA中的冗余Radix-2R编号系统提供硬件算法，以加快具有许多位的数字的算术操作，这些数字在RSA加密和解密等安全系统中具有应用。我们的硬件算法加速了算术操作，包括添加，乘法和蒙哥马利模型乘法。令人惊讶的是，我们的乘法的硬件算法和两个1024位数的乘法和蒙特哥利乘法仅使用冗余radix-216-216数字系统运行64个时钟循环。同样，Xilinx virtex-ii Pro家族FPGA XC2VP100-6的实验结果表明，我们电路的时钟频率与位数无关。使用常规数字系统的冗余编号系统的硬件算法的加速因子为1024位添加的速度系统为8.3，1024位乘法为3.4，对于1024位蒙哥马利模式乘法，为2.5。此外，对于256位Montgomery Modulo乘法，我们的硬件算法以0.38 MUS运行，而先前已知的实现在1.22 MUS中运行。因此，我们使用冗余数系统进行算术操作的方法非常有效。
The main contribution of this paper is to present hardware algorithms for redundant radix-2r number system in the FPGA to speed the arithmetic operations for numbers with many bits, which have applications in security systems such as RSA encryption and decryption. Our hardware algorithms accelerate arithmetic operations including addition, multiplication, and Montgomery modulo multiplication.Quite surprisingly, our hardware algorithms of the multiplication and Montgomery multiplication for two 1024-bit numbers runs only 64 clock cycles using redundant radix-216 number system. Also, the experimental results for Xilinx Virtex-II Pro Family FPGA XC2VP100-6 show that the clock frequency of our circuit is independent of the number of bits. The speed up factors of our hardware algorithm using the redundant number system over those using the conventional number system are 8.3 for 1024-bit addition, 3.4 for 1024-bit multiplication, and 2.5 for 1024-bit Montgomery modulo multiplication. Further, for 256-bit Montgomery modulo multiplication, our hardware algorithm runs in 0.38 mus, while a previously known implementation runs in 1.22 mus. Thus, our approach using redundant number system for arithmetic operations is very efficient.