A high-radix hardware algorithm for calculating the exponential M/sup E/ modulo N
A high-radix hardware algorithm for calculating the exponential M/sup E/ modulo N
复制标题
用于计算指数 M/sup E/ 模 N 的高基数硬件算法
DOI：
10.1109/arith.1991.145533
复制
发表时间：
1991
期刊：
影响因子：
--
通讯作者：
Peter Kornerup
中科院分区：
文献类型：
--
作者：
Holger Orup;Peter Kornerup
在一类密码系统中，模指数的快速计算是必不可少的。作者提出了一个并行版本的一个著名的指数算法，一半的最坏情况下的计算时间。描述了如何通过将串行-并行乘法方案与SRT除法方案交织来实现高基数模乘法。通过使用中间操作数的冗余表示，有效地解决了与高基数相关的问题。它示出了如何算法可以实现为一个高度正规的VLSI电路。仿真表明，该算法的基数32实现能够在3.2 ms内计算512-B操作数指数。这比其他已知实现快五倍以上。<<ETX>>
In a class of cryptosystems, fast computation of modulo exponentials is essential. The authors present a parallel version of a well-known exponentiation algorithm that halves the worst-case computing time. It is described how a high radix modulo multiplication can be implemented by interleaving a serial-parallel multiplication scheme with an SRT division scheme. The problems associated with high radices are efficiently solved by the use of a redundant representation of intermediate operands. It is shown how the algorithms can be realized as a highly regular VLSI circuit. Simulations indicate that a radix 32 implementation of the algorithms is capable of computing 512-b operand exponentials in 3.2 ms. This is more than five times faster than other known implementations.<<ETX>>