方幂模快速计算的二进制分组查表法

摘要：

在方幂模的二进制快速算法基础上,进一步改写方幂模计算表达式,设计了一种基于查表法的二进制快速算法.算法将指数的二进制形式进行分组,提前计算并记忆一个二进制分组中首位为1其他位任意变化的所有情况下的方幂模结果,然后遍历指数的二进制形式,按照算法规则直接平方或连续多次平方后与事先记忆的值相乘,已经记忆的值不需要重复计算,从而减少了大量的乘法运算.算法分析和实验结果证明,基于查表法的方幂模二进制快速算法比二进制算法减少了乘法次数,尤其指教二进制形式中有大量1连续出现或相对连续出现(同一分组内有两位以上为1)的情况下算法效率比二进制算法有大幅度提高.

关键词：RSA算法、方幂模、二进制算法、二进制分组查表法

所属期刊栏目：45

分类号：TP301(计算技术、计算机技术)

资助基金：国家自然科学基金the National Natural Science Foundation of China under Grant 60673153,60773053.60803048;山东省自然科学基金the Natural Science Foundation of Shandong Province of China under Grant Y2005G09,Y2007A28

在线出版日期：2009-09-03（万方平台首次上网日期，不代表论文的发表时间）

页数：共2页

页码：71-72