面向嵌入式处理器的优化Montgomery模乘算法
发布时间：2018-09-13 15:59
【摘要】：针对嵌入式系统中频繁的内存存取影响Montgomery模乘算法效率的问题,提出了一种优化的分离连续操作数缓存算法。该算法基于连续操作数缓存算法并进行优化,应用于计算多精度乘法和约减两部分,将整个计算分块使得每块内操作数只被加载一次;为了不破坏操作数加载的连续性,在多精度乘法和约减之间采用分离集成的方式;通过动态地使用寄存器和有效的缓存操作数来减少嵌入式系统中算法使用内存存取操作的总量,实现提高模乘算法效率的目的。实验结果表明:在使用MIPS64架构的处理器上,当模数为1 024bit时,与应用广泛的粗粒度集成操作数扫描算法相比,该算法的效率提高了4.17%。在嵌入式系统中,可将该算法应用于公钥密码体系中的模乘运算,在提高模乘效率的同时提高公钥密码算法的运算效率。
[Abstract]:In order to solve the problem that frequent memory access in embedded systems affects the efficiency of Montgomery modular multiplication algorithm, an optimized discrete continuous Operand buffer algorithm is proposed. The algorithm is based on the continuous Operand Cache algorithm and optimized. The algorithm is applied to the computation of multiple precision multiplication and reduction. The whole calculation block is divided so that the operands in each block are loaded only once, so that the continuity of Operand loading is not broken. In order to improve the efficiency of the modular multiplication algorithm, the method of separation and integration between multi-precision multiplication and reduction is adopted, and the total amount of memory access operations in embedded system is reduced by using registers and effective cache operands dynamically. The experimental results show that the efficiency of this algorithm is 4.1717 higher than that of coarse-grained integrated Operand scanning algorithm when the modulus is 1 024bit on the processor with MIPS64 architecture. In the embedded system, the algorithm can be applied to the modular multiplication operation in the public key cryptosystem, which not only improves the efficiency of modular multiplication, but also improves the efficiency of the public key cryptosystem.
【作者单位】： 中国科学院声学研究所国家网络新媒体工程技术研究中心;中国科学院大学电子电气与通信工程学院;
【基金】：中国科学院战略性先导科技专项课题资助项目(XDA06010302);中国科学院声学研究所知识创新工程资助项目(Y154191601)
【分类号】：TP332
[Abstract]:In order to solve the problem that frequent memory access in embedded systems affects the efficiency of Montgomery modular multiplication algorithm, an optimized discrete continuous Operand buffer algorithm is proposed. The algorithm is based on the continuous Operand Cache algorithm and optimized. The algorithm is applied to the computation of multiple precision multiplication and reduction. The whole calculation block is divided so that the operands in each block are loaded only once, so that the continuity of Operand loading is not broken. In order to improve the efficiency of the modular multiplication algorithm, the method of separation and integration between multi-precision multiplication and reduction is adopted, and the total amount of memory access operations in embedded system is reduced by using registers and effective cache operands dynamically. The experimental results show that the efficiency of this algorithm is 4.1717 higher than that of coarse-grained integrated Operand scanning algorithm when the modulus is 1 024bit on the processor with MIPS64 architecture. In the embedded system, the algorithm can be applied to the modular multiplication operation in the public key cryptosystem, which not only improves the efficiency of modular multiplication, but also improves the efficiency of the public key cryptosystem.
【作者单位】： 中国科学院声学研究所国家网络新媒体工程技术研究中心;中国科学院大学电子电气与通信工程学院;
【基金】：中国科学院战略性先导科技专项课题资助项目(XDA06010302);中国科学院声学研究所知识创新工程资助项目(Y154191601)
【分类号】：TP332
【相似文献】
相关期刊论文 前10条
1 刘铎,宋涛,戴一奇;Isomorphism and Generation of Montgomery-Form Elliptic Curves Suitable for Cryptosystems[J];Tsinghua Science and Technology;2005年02期
2 王喜成,张振华;预计算式Montgomery算法研究[J];桂林电子工业学院学报;2001年03期
3 陈昭智,郑建德;Montgomery算法在大数模幂运算中的改进[J];厦门大学学报(自然科学版);2004年S1期
4 李明久;季晓勇;刘鞭箭;;Montgomery算法分析与研究[J];科学技术与工程;2006年12期
5 靳蓓蓓;张仕斌;;Montgomery模幂运算的一种改进方案[J];长春大学学报;2006年08期
6 邓锐;周玉洁;;Montgomery逆算法的改进和应用[J];计算机科学;2006年05期
7 李明久;;Montgomery算法分析与应用改进[J];计算机工程与应用;2007年01期
8 王金荣;周，
本文编号：2241654
本文链接：https://www.wllwen.com/kejilunwen/jisuanjikexuelunwen/2241654.html
