文献类型：期刊文章

作　　者：王念平[1] 金晨辉[1]

机构地区：[1]解放军信息上程大学电子技术学院,河南郑州450004

出　　处：《电子学报》

基　　金：现代通信国家重点实验室基金(No.5143603ZDS0601);河南省杰出青年科学基金(No.0312001800)

年　　份：2008

卷　　号：36

期　　号：1

起止页码：133-135

语　　种：中文

收录情况：BDHX、BDHX2004、CAS、CSA、CSA-PROQEUST、CSCD、CSCD2011_2012、EI(收录号：20081511196373)、IC、INSPEC、JST、RCCSE、RSC、SCOPUS、ZGKJHX、核心刊

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

关 键 词：大整数相乘问题  分治算法 计算复杂度

分 类 号：TP391]