Montgomery逆算法的改进和应用  

Improvement to Montgomery Modular Inverse Algorithm

作　　者：邓锐[1] 周玉洁[1] 

机构地区：[1]解放军信息工程大学信息研究系,郑州450002

出　　处：《计算机科学》2006年第5期124-127,共4页Computer Science

基　　金：863基金项目2003AAIZ1270

摘　　要：本文通过对 Montgomery 逆算法核心部分的改进,得到两种分别以4为基和8为基的优化算法。其中以4为基的算法,在基本不增加算法实现复杂度的情况下,使迭代次数的平均上限从2n 降到7/6n,平均迭代次数也从3n/2降到了7/8n。而8基算法则相应分别下降到28/24n 和25/32n,但算法内部的比较和跳转稍有增多。由于新算法只要求两个关键操作数中有一个变成1,就可以结束操作(原算法要求两个都变为1),因此实际迭代次数可能还要少。本文提出的算法也可以运用在文[1,2,7]中求基本模逆的算法中。本文算法主要适用于软件实现,在 RSA 和 ECC 等公钥体制实现中有广泛的应用。After a comprehensive investigation of the Montgomery modular inverse algorithm and its refined versions, we present two modified high radix algorithms. The 4-radix algorithm can reduce the average upper limit of the number of iterations from 2n to 7/6n, and the average number of iterations from 3n/2 to7/8n while adding little complexity. And the 8-radix one can reduce the related number of iterations to 25/24n and 25/32n, but there are more comparisons and branches. For the new algorithms terminate when one of the two key operands, rather than both, is reduced to 1, the actual number of iterations may be even smaller than the ones above. The new algorithms can also be used in algorithms in [1, 2,7] to get classical modular inverse. The proposed algorithms are suitable for software implementations on general-purpose microprocessors, and can be used in public key cryptographic applications such as RSA and ECC.

关 键 词：Montgomery逆算法 模逆 公钥加密算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]