大数乘法即多项式乘法问题，求A(x)与B(x)的乘积C(x)，朴素解法的复杂度是O(n^2)
Karatsuba算法，复杂度约为O(n^log3)
基本思想是把多项式A(x)与B(x)写成
A(x)=a*x^m+b
B(x)=c*x^m+d
其中a,b,c,d为x的多项式。
则A(x)*B(x)=(ac)*x^2m+(ad+bc)*x^m+bd
由ad+bc=(a+b)(c+d)-ac-bd
原来的4次乘法和1次加法由3次乘法和2次减法代替，减少了一次乘法操作。
用同样的方法应用到abcd的乘法上。
Toom-cook算法
Toom-cook是Karatsuba算法的一般化，把A(x)与B(x)分成k部分，从而更多地减少乘法次数。Toom-cook的复杂度是Θ(c(k)*n^e)，其中e=log(2k-1)/log(k)。k增大时n^e减小，而c(k)增加。
Karatsuba算法即Toom-2算法，通常使用的是Toom-3。它把A(x)与B(x)分成3部分，这样结果多项式的次数最大为4。取5个特殊值vk，计算A(vk)与B(vk)，则C(vk)=A(vk)*B(vk)，有了vk与C(vk)，可采用矩阵求逆的方法求出C(x)的系数。
对于确定的k，vk的值是常数，这样矩阵的逆及逆矩阵与结果向量相乘的运算都可提前计算好。
Toom-3使用的vk是0,1,-1,-2和∞。
Schönhage–Strassen算法
该算法的思想与Toom-cook算法有一点相似，它不划分A(x)与B(x)，如果可以直接找出2n-1个点pk以及计算出A(pk)和B(pk)，则同样得到了pk与C(pk)，再还原出系数即可。
取这2n-1个点为单位复根，把多项式从系数表示转化到点对表示以及由点对表示还原到系数表示采用了FFT。FFT的复杂度是O(nlogn)，中间的点乘是Θ(n)，所以总体复杂度为O(nlogn)
