Montgomery逆算法的改进和应用

• 作者: 周玉洁 邓锐
• 来源期刊: 计算机科学
• 学科: 工学
• 关键词: Montgomery逆算法 模逆 公钥加密算法
• 年，卷（期）: 2006,（5）
• 所属期刊栏目: 计算机网络与信息技术
• 页码范围: 124-127
• 页数: 4页
• 分类号: TP3
• 字数: 5536字
• 语种: 中文
• DOI: 10.3969/j.issn.1002-137X.2006.05.032

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	周玉洁	解放军信息工程大学信息研究系	2	3	1.0	1.0
2	邓锐	解放军信息工程大学信息研究系	1	0	0.0	0.0