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

A proposed Montgomery ladder algorithm and architectures

作　　者：袁仕继[1] 李博章[1] 孙慧慧[1] 张广吉[1] 

机构地区：[1]中国人民解放军63888部队

出　　处：《微型机与应用》2013年第11期78-80,共3页Microcomputer & Its Applications

摘　　要：提出了利用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.

关 键 词：模幂运算 标量乘 Montgomery阶梯算法 

分 类 号：TP39[自动化与计算机技术—计算机应用技术]