用分治算法求大整数相乘问题的进一步分析

• 作者: 王念平 金晨辉
• 来源期刊: 电子学报
• 学科: 工学
• 关键词: 大整数相乘问题 分治算法 计算复杂度
• 年，卷（期）: 2008,（1）
• 所属期刊栏目: 学述论文
• 页码范围: 133-135
• 页数: 3页
• 分类号: TP391
• 字数: 3259字
• 语种: 中文
• DOI: 10.3321/j.issn:0372-2112.2008.01.024

摘要

对利用分治算法解决大整数相乘问题作了进一步深入的研究和分析.在原来的分治算法的基础上,将输入规模为n的两个大整数各分成规模相等的k(2≤k≤n)部分,证明了通过恒等变形可将其乘积中的k2次乘法降为k(k+1)/2次;给出了计算两个大整数乘积的计算复杂度;证明了利用分治算法将两个大整数各分成规模相等的两部分来进行处理时的计算复杂度是最小的,进而表明利用分治算法将大整数各分成规模相等的两部分来进行处理是合理的.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	金晨辉	解放军信息工程大学电子技术学院	72	462	11.0	18.0
2	王念平	解放军信息工程大学电子技术学院	28	195	6.0	13.0