查询结果:   高雪寒,高丽丽,李顺东.面向公钥密码体系的大数相除快速算法[J].计算机应用与软件,2014,31(6):275 - 277,323.
中文标题
面向公钥密码体系的大数相除快速算法
发表栏目
算法
摘要点击数
612
英文标题
FAST ALGORITHM OF LARGE INTEGER DIVISION FOR PUBLIC KEY CRYPTOGRAPHIC SYSTEM
作 者
高雪寒 高丽丽 李顺东 Gao Xuehan Gao Lili Li Shundong
作者单位
陕西师范大学计算机科学学院 陕西 西安 710062     
英文单位
School of Computer Science, Shaanxi Normal University, Xi’an 710062, Shaanxi, China     
关键词
大整数相除 预处理 快速算法 窗口滑动
Keywords
Large integer division Preprocessing Fast algorithm Window sliding
基金项目
国家自然科学基金面上项目(61070189/61272435)
作者资料
高雪寒,硕士生,主研领域:信息安全与密码学。高丽丽,硕士。李顺东,教授。 。
文章摘要
[JP+1]模运算是公钥密码学的一种基本运算。做模运算前提需要做除法运算,因此除法运算也是密码学的基本运算。大整数除法的运算速度是影响公钥密码体系中效率的关键因素。针对大数相除问题,提出大数相除的快速改进算法,其基本思想是,以空间换取时间。首先,通过建立预处理表,减少试除法中大数乘法的次数,从而高效快速得出商值;然后,运用窗口滑动方法来提高大数减法的速度。实验结果表明,该算法可以提高密码学算法的运算效率。算法时间复杂度为O(n),空间复杂度为O(n)。
Abstract
Modular operation is a basic operation in public key cryptography. To do the division operation is the prerequisite of doing modular operation, so the division operation is also a basic operation in cryptography. The speed of large integer division operation is a key factor affecting the efficiency of public key cryptology. In light of the large integer division issue, we present an improved fast algorithm for large integer division, its basic idea is to speed up the computation by storing some information. First, we reduce the numbers of large integer multiplications in trial division method by establishing a preprocessing table, so as to efficiently and quickly get the quotient value; then we improve the speed of the integer subtraction by using windows sliding method. Experimental results show that the proposed algorithm can raise the operation efficiency of cryptography algorithm. The time complex degree of the algorithm is O(n), and the space complex degree is O(n).
下载PDF全文