一种改进的Montgomery阶梯算法及其实现

A proposed Montgomery ladder algorithm and architectures

提出了利用Montgomery阶梯算法实现快速模幂运的两种方案。第一种是将每个时钟周期内乘法和平方并行执行,且使用2×2正交变换器选择输出,使Montgomery阶梯算法简单、高效;第二种是使用循环展开技术将循环数减少一半,且只需要一半的时钟,运算效率得到更大的提高。

In this paper, two efficient architectures for modular exponentiation respectively using Montgomery ladder algorithm are proposed. The first one is a straightforward and efficient implementation of the Montgomery ladder algorithm, in which the muhiplieation and squaring are performed in parallel during each clock cycle. A novel designed two-by-two cross-point switch is used to select each ladder step. By parallelizing the Montgomery ladder using loop unrolling technique so that the number of loops is reduced by half, a second efficient architecture is proposed that requires only half number of clock cycles compared to the first one.