Montgomery逆算法的改进和应用

计算机科学 ›› 2006, Vol. 33 ›› Issue (5): 124-127.

Montgomery逆算法的改进和应用

邓锐周玉洁

解放军信息工程大学信息研究系,郑州450002

出版日期:2018-11-17 发布日期:2018-11-17
基金资助:
863基金项目2003AAIZ1270.

DENG Rui ,ZHOU Yu-Jie （Information Research Department of PLA Information Project University, Zhengzhou 450002）

Online:2018-11-17 Published:2018-11-17

摘要/Abstract

摘要： 本文通过对Montgomery逆算法核心部分的改进，得到两种分别以4为基和8为基的优化算法。其中以4为基的算法，在基本不增加算法实现复杂度的情况下，使迭代次数的平均上限从2n降到7/6n，平均迭代次数也从3n/2降到了7/8n。而8基算法则相应分别下降到25/24和25/32n，但算法内部的比较和跳转稍有增多。由于新算法只要求两个关键操作数中有一个变成1，就可以结束操作（原算法要求两个都变为1），因此实际迭代次数可能还要少。本文提出的算法也可以运用在文[1，2，7]中求基本模逆的算法中。本文算法主要适用于

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

Abstract: 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,

Key words: Montgomery modular inverse, Modular inverse, Public key cryptographic algorithm

邓锐周玉洁. Montgomery逆算法的改进和应用[J]. 计算机科学, 2006, 33(5): 124-127. https://doi.org/

DENG Rui ,ZHOU Yu-Jie （Information Research Department of PLA Information Project University, Zhengzhou 450002）. [J]. Computer Science, 2006, 33(5): 124-127. https://doi.org/

参考文献

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed