摘要:对利用分治算法解决大整数相乘问题作了进一步深入的研究和分析,在原来的分治算法的基础上,将输入规模为n的两个大整数各分成规模相等的k(2≤k≤n)部分,证明了通过恒等变形可将其乘积中的k^2次乘法降为k(k+1)/2次;给出了计算两个大整数乘积的计算复杂度;证明了利用分治算法将两个大整数各分成规模相等的两部分来进行处理时的计算复杂度是最小的,进而表明利用分治算法将大整数各分成规模相等的两部分来进行处理是合理的。
关键词:大整数相乘问题 分治算法 计算复杂度
单位:解放军信息上程大学电子技术学院; 河南郑州450004
注:因版权方要求,不能公开全文,如需全文,请咨询杂志社