Abstract: This paper focus on the algorithm to reduce the number of multiplication for two numbers and thus reduces the computational complexity from O(n) to O(1). According to different addition operation methods, two improved algorithms(ie. cumulative sum and uniform sum) are introduced and their time-cost is compared with that of the current large integer multiplication algorithm.

Key words: large integer multiplication, divide and conquer algorithm, cumulative summing, fast algorithm, uniform summing

摘要： 利用分治法思想，提出一种大整数相乘快速算法，减少乘法运算次数，使2个数相乘的计算复杂度从O(n)降低到O(1)。根据不同的加法思路，提出累加求和及统一求和2种改进算法，给出2种改进算法的形式化描述，并通过实验给出改进算法和现有的典型大整数位相乘算法的时间比较。研究结果表明，该算法能够提高密码算法和信息安全协议的运算效率。

关键词: 大整数相乘, 分治法, 累加求和, 快速算法, 统一求和

CLC Number: 

• TP301.6