-
题名方幂模快速计算的二进制分组查表法
被引量：2
- 1
-
-
作者
董付国
厉玉蓉
杜萍
-
机构
山东工商学院计算机科学与技术学院
山东大学计算机科学与技术学院
-
出处
《计算机工程与应用》
CSCD
北大核心
2009年第22期71-72,共2页
-
基金
国家自然科学基金No.60673153
No.60773053
+2 种基金
No.60803048
山东省自然科学基金No.Y2005G09
No.Y2007A28~~
-
文摘
在方幂模的二进制快速算法基础上,进一步改写方幂模计算表达式,设计了一种基于查表法的二进制快速算法。算法将指数的二进制形式进行分组,提前计算并记忆一个二进制分组中首位为1其他位任意变化的所有情况下的方幂模结果,然后遍历指数的二进制形式,按照算法规则直接平方或连续多次平方后与事先记忆的值相乘,已经记忆的值不需要重复计算,从而减少了大量的乘法运算。算法分析和实验结果证明,基于查表法的方幂模二进制快速算法比二进制算法减少了乘法次数,尤其指数二进制形式中有大量1连续出现或相对连续出现(同一分组内有两位以上为1)的情况下算法效率比二进制算法有大幅度提高。
-
关键词
RSA算法
方幂模
二进制算法
二进制分组查表法
-
Keywords
RSA algorithm
modular exponentiation
binary algorithm
binary partition table search algorithm
-
分类号
TP301
[自动化与计算机技术—计算机系统结构]
-
-
题名几种方幂模快速算法的加法链一致性分析
被引量：3
- 2
-
-
作者
董付国
厉玉蓉
-
机构
山东工商学院计算机科学与技术学院
-
出处
《计算机工程与应用》
CSCD
北大核心
2010年第36期48-50,55,共4页
-
基金
国家自然科学基金(No.60673153
No.60773053
+3 种基金
No.60803048)
山东省自然科学基金(No.Y2005G09
No.Y2007A28)
山东省高校科研发展计划项目(No.J10LG21)~~
-
文摘
在RSA算法中,最主要、使用最频繁同时也是最耗时的是方幂模运算。自从RSA算法提出后,方幂模快速算法一直是研究重点之一,方幂模算法的改进和速度的提高直接影响RSA算法的整体性能和广泛应用。深入分析了方幂模计算的秦九韶算法、分块算法、二进制自适应分组查表法和最短加法链算法,提出了加法链的统一思想,认为这几种算法在本质上都是加法链算法,为以后的研究工作指出了方向。同时指出二进制自适应分组查表法可以获得更高的整体效率,但仍有进一步提升的空间。
-
关键词
方幂模
秦九韶算法
分块算法
二进制自适应分组查表法
加法链
-
Keywords
modular exponentiation
Qin Jiu-shao algorithm
blocking algorithm
adaptive binary partition table searching meth-oda
ddition chains
-
分类号
TP301
[自动化与计算机技术—计算机系统结构]
-
