大整数算法:使用分治法的思想,就是把一些大的位数的整数进行一定程度的拆分,然后分别求解,最后合并为原问题的乘积。

这里我们假设有两个大整数X、Y,分别设X=1234、Y=5678。现在要求X*Y的乘积,那我们可以采用分治的算法,将X、Y分别拆分为A与B、C与D,如下图:

 (1)

  1. 首先将X和Y分成A,B,C,D四个部分
  2. 此时将X和Y的乘积转化为(1)式,把问题转化为求解因式分解的值
  3. 由此可知X=A2的(n/2)次方+B,Y=C2的(n/2)+D,所以X和Y的乘积为XY=。。。。。。