模指数运算的一种快速实现算法  

Efficient Implementation for Modular Exponentiation

作　　者：何桂荣[1] 宋宗余[2] 

机构地区：[1]中山火炬职业技术学院公共课教学部,广东中山528436 [2]郑州师范学院初等教育学院,河南郑州450053

出　　处：《通信技术》2017年第5期1045-1049,共5页Communications Technology

摘　　要：模指数运算是RSA和Elgama等公钥密码系统中的一个重要模块。提高模指数运算的效率,对提高公钥密码系统的可行性具有重要意义。提高模指数运算的方法主要有两种,一种是减少循环的长度次数,一种是减少循环中的乘法和求逆运算的次数。通过将指数采用双基链表示来减少循环长度,并通过预计算避免耗时较大的求逆运算。因此,模指数运算的效率得到了很大提高。最后,通过对不同类型的算法进行测试,结果表明,所提算法比以前的算法在效率上有一定的提高。In public key cryptosystem such as RSA and Elgama etc, modular exponentiation is an important module. The improvement on the efficiency of modular exponentiation plays an important role in ascending the feasibility of public-key cryto system . Two methods are involved, one is to reduce the length of loop; the other to decrease the number of multications and inversions. The length of loop is reduced by applying the double-base presentation of the exponent; and time wasting inversion is avoided by pre-computation. Thus the efficiency of modular exponentiation is obviously improved. Finally, the experiments on various algorithms are indicate that the proposed algorithm is more efficient than previous ones.

关 键 词：公钥加密 密钥协商 模指数运算 双基链 

分 类 号：TP3[自动化与计算机技术—计算机科学与技术]