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

摘要

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