摘要
利用分治法思想,提出一种大整数相乘快速算法,减少乘法运算次数,使2个数相乘的计算复杂度从O(n)降低到O(1)。根据不同的加法思路,提出累加求和及统一求和2种改进算法,给出2种改进算法的形式化描述,并通过实验给出改进算法和现有的典型大整数位相乘算法的时间比较。研究结果表明,该算法能够提高密码算法和信息安全协议的运算效率。
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 0（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.
出处
《计算机工程》
CAS
CSCD
2012年第16期121-123,共3页
Computer Engineering
基金
国家自然科学基金资助项目"高性能保密计算算法与协议研究"(61070189)
陕西省科技攻关基金资助项目"用数据挖掘研究地震余震预报与综合评判"(2008K01 58)
关键词
大整数相乘
分治法
累加求和
快速算法
统一求和
large integer multiplication
divide and conquer algorithm
cumulative summing
fast algorithm
uniform summing
