论文研究Montgomery模乘算法的改进及其应用.pdf

Montgomery算法是目前最适合于通用处理器软件实现的大整数模乘算法。1996年，Koc总结了该算法的五种实现方法：SOS、CIOS、FIOS、FIPS和CIHS，并指出CIOS方法综合性能较优。首先深入分析了FIOS实现方法，并通过消除进位传递和减少循环控制等手段，提出了一种改进方法IFIOS。然后将该方法应用于模幂计算，给出了基于滑动窗口技术的Montgomery模幂算法。最后理论分析和实验结果表明，该改进将FIOS的执行速度提高了约54%，与目前常用的CIOS方法相比，亦有较大的优势。