一种用于公钥密码系统的新型可变Radix快速乘法硬件算法

A novel Variable Radix Fast Multiplication Hardware Algorithm for public-Key Cryptosystem

本文提出了一种新型的可变ｒａｄｉｘ快速乘法硬件算法，算法中，采用了二进制数的冗余数表示方法，使二个大数（大到５１２ｂｉｔ位或更大）的相加在Ｏ（１）时间内完成而无需等待进位；其次，提出了可变ｒａｄｉｘ快速乘法思想，使算法比ｒａｄｉｘ－４的乘法算法速度提高３３％，比ｒａｄｉｘ－８的乘法算法速度提高１１％而硬件实现更为简单，算法还能克服在较坏和最坏条件下，ｒａｄｉｘ－８乘法算法速度严重下降的缺陷，是一种可以作为核心运算有效地使用在许多公钥密码体制（如ＲＳＡ）硬件ＶＬＳＩ实现中的新型快速算法。

A novel variable radix fast multiplication algorithm is presented. In the algorithm,redundant binary representation is adopted to carry out addition of two big numbers (512 bits or more)without carry propagation. The idea of variable radix fast multiplication is proposed. It makes the algorithm 33% more efficient than the radix-4 multiplication algorithm,and 11% more efficient than the radix-8 multiplication algorithm. Compared with the radix-8 multiplication algorithm, its hardware realization is simpler and it can overcome the radix-8 algorithm's drawback that efficiency is seriously descended at worse and worst conditions. As a kernal,it is efficient for the hardware VLSI implementation for many public-key cryptosystems such as RSA cryptosystem.