面向公钥密码体系的大数相除快速算法

FAST ALGORITHM OF LARGE INTEGER DIVISION FOR PUBLIC KEY CRYPTOGRAPHIC SYSTEM

模运算是公钥密码学的一种基本运算。做模运算前提需要做除法运算,因此除法运算也是密码学的基本运算。大整数除法的运算速度是影响公钥密码体系中效率的关键因素。针对大数相除问题,提出大数相除的快速改进算法,其基本思想是,以空间换取时间。首先,通过建立预处理表,减少试除法中大数乘法的次数,从而高效快速得出商值;然后,运用窗口滑动方法来提高大数减法的速度。实验结果表明,该算法可以提高密码学算法的运算效率。算法时间复杂度为O(n),空间复杂度为O(n)。

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）.