改进的大整数相乘快速算法

作者：周健; 李顺东; 薛丹

来源：计算机工程, 2012, (16): 121-123.

• 大整数相乘
• 分治法
• 累加求和
• 快速算法
• 统一求和 large integer multiplication
• divide and conquer algorithm
• cumulative summing
• fast algorithm
• uniform summing

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

• 出版日期2012
• 单位陕西师范大学