基于FFT的大整数乘法

基于FFT的大整数乘法1背景对于两个长度为n的大整数，普通的大整数乘法的时间复杂度是2nO，而采用一种精心构造的分治算法，则可以将时间复杂度降低为585.13log2nOnO。此处则是受到快速傅立叶变换算法的启发，提出一种新的大整数乘法，该算法基于模-p的有限域运算，采用类似于FFT的算法，可以将大整数乘法的时间复杂度降低为5.1nO，甚至，从某种意义上说，可以达到nnOlog。2基础2.1FFT（可以参考《算法导论》及《算法概论》相关内容）对于两个n-1次多项式3基于FFT的大整数乘法3.1大整数的表示方法为简便起见，这里只考虑10进制大整数，但是这样并不会失去其一般性。对于一个10进制整数，可以将其表示为：01221110101010aaaaAnnnn这样，就可以将一个大整数对应到一个n-1次多项式上去：012211axaxaxaxANnnnnA，其中9,8,7,6,5,4,3,2,1,0ia3.2大整数的乘法对于两个十进制大整数AN和BN，设AN各个位上的数字如下：0121aaaann而BN各个位上的数字如下：0121bbbbnn另外记多项式012211axaxaxaxAnnnn，012211bxbxbxbxBnnnn于是有10ANA，10BNB。记大整数BACNNN，多项式xBxAxC则有：101010CBANNNBAC于是已知AN和BN，要得到CN，可以采用如下方法：于是，关键的问题是找到一个有效的算法以计算xBxAxC。可惜的是，传统的FFT算法是基于复数上的n次单位根ninn2sin2cos的，因此必须要进行三角函数之类的浮点运算，从而会有一定程度的误差。那么问题在于能否找到一个合适的方法来进行整系数多项式的乘法而没有任何的误差呢？据笔者所知，还没有一种十分合适的类似于FFT的针对于一般的整系数多项式的乘法。但是，大整数乘法中所要用到的多项式乘法十分特殊：即两个因子多项式中，每一个系数都不大于10.因此下面所要找的，就是对于这样一种特殊的整系数多项式的比较合适的乘法算法。我们的工具是模-p的有限域。首先，如果我们在模-p的有限域上能够计算出：pxBxAxCmod'即有220,mod'nipccii，又根据多项式乘法可以知道，1818199,1,0,1,0,1,0nbacikjnkjikjnkjikjnkjkji，因此如果我们挑选一个足够大的p使得181np，则可知pci，又有：pci',pcciimod'，从而可知iicc'.3.3关于p的选择0121aaaann0121bbbbnn012211axaxaxaxAnnnn012211bxbxbxbxBnnnn0132322222cxcxcxcxCnnnn''''013222ccccnnlinertimelinertimetime???于是我们现在需要做的就是对于给定的一个数p，设计一个类似于FFT的算法，求出pxBxAxCmod'。我们可以将p的取值范围缩小一点，针对于p为素数，且p足够大（显然要大于2n-2）的情况来讨论。这个任务其实就是要证明在模-p的域上的“n次单位根”具有与复数域上的n次单位根类似的性质。即证明模-p的域上的FFT算法是合法的。【定理1】模-p乘法群是p-1阶循环群。【证明】此定理等价于同余方程pxpmod11有p-1次本原单位根。这个定理的证明可以参考《数论概论》中关于模-p的本原根的内容。在一般的近世代数教材中也会有这一内容。■由此，记m=p-1,于是可以找到一个次单位根。由于pn,所以m=p-1n.从而A（x）和B（x）都可以表示成m-1次多项式。0111aaaAmm将此xA分成两部分：22211122121222xxAxAxaxxaxAmkkkmkkk于是2221xxAxAxA，2221xxAxAxA由上式可知，要计算xA和xA，只需要先计算21xA和22xA，然后再做一次乘法、一次加法和一次减法即可，要计算k个自变量的函数，需要的时间是：12/2kkTkT，从而可得mmOmTlog。由上面的式子可以看出，要想进行FFT变换，其关键在于对于n个自变量m,...,,2求它们的函数的问题可以转化为求m,...,,42对于另外一些多项式的函数问题。但是问题是在进行逆变换时必须要满足pmkkmod01，根据等比数列公式pmmkkmod0111，这样必有1m，也就是说，必须找到n次单位根。根据群论中的Lagrange定理，m|p-1，从而p-1必须精心选择，使得它包含较多的素因子2.事实上，必须满足两个条件：折半引理和求和引理。求和引理已经在上一段描述过了。折半引理指的是imi2/。因为只有这样我们才能够实施分治策略。网络上有一种算法，是直接找出一个符合条件的大的素数p。这种方法有不完美之处：当n变得很大，超出了p的范围时，该算法就不适用了。当然，这种方法已经能够满足现实中的大部分需求了。而且由于是事先计算好的模-p的域，因而节省了大量的工作，其时间性能比较好。我们的目的是寻找一种好的方法，使得该算法能够更容易地扩展，以适应任何长度的大整数。关于p为素数的情况，现在貌似也找不到一种好的方法来。对于合数的情况，参见《基于快速傅立叶变换的大整数乘法研究》这篇论文。虽然其定理十分优美，但是没有实用性。因为它所选取的合数c对n成指数级。即12nc。这样在做运算的时候就失去了大整数乘法的时间优势，相当于白费力。