基于fft的大整数乘法

《基于fft的大整数乘法》由会员分享，可在线阅读，更多相关《基于fft的大整数乘法（4页珍藏版）》请在金锄头文库上搜索。

1、基于 FFT 的大整数乘法1 背景对于两个长度为的大整数，普通的大整数乘法的时间复杂度是，而n 2nO采用一种精心构造的分治算法，则可以将时间复杂度降低为。585. 13log2nOnO此处则是受到快速傅立叶变换算法的启发，提出一种新的大整数乘法，该算法 基于模-p 的有限域运算，采用类似于 FFT 的算法，可以将大整数乘法的时间复杂度降低为，甚至，从某种意义上说，可以达到。 5 . 1nOnnOlog2 基础2.1 FFT（可以参考算法导论及算法概论相关内容）对于两个 n-1 次多项式3 基于 FFT 的大整数乘法3.1 大整数的表示方法为简便起见，这里只考虑 10 进制大整数，但是这样并不

2、会失去其一般性。 对于一个 10 进制整数，可以将其表示为： 012 21 110101010aaaaAn nn n L这样，就可以将一个大整数对应到一个 n-1 次多项式上去：，其中 012 21 1axaxaxaxANn nn nA La9 , 8 , 7 , 6 , 5 , 4 , 3 , 2 , 1 , 0ia3.2 大整数的乘法对于两个十进制大整数和，设各个位上的数字如下：ANBNAN0121aaaannL而各个位上的数字如下：BN0121bbbbnnL另外记多项式， 012 21 1axaxaxaxAn nn n L 012 21 1bxbxbxbxBn nn n L于是有，。 1

3、0ANA 10BNB记大整数，多项式则有：BACNNN xBxAxC 101010CBANNNBAC于是已知和，要得到，可以采用如下方法：ANBNCN0121aaaannL0121bbbbnnL 012 21 1axaxaxaxAn nn n L 012 21 1bxbxbxbxBn nn n L 0132 3222 22cxcxcxcxCn nn n L013222ccccnnLliner timeliner timetime?于是，关键的问题是找到一个有效的算法以计算。可惜的 xBxAxC是，传统的 FFT 算法是基于复数上的 n 次单位根的，因此ninn2sin2cos必须要进行三角函数

4、之类的浮点运算，从而会有一定程度的误差。那么问题在 于能否找到一个合适的方法来进行整系数多项式的乘法而没有任何的误差呢？ 据笔者所知，还没有一种十分合适的类似于 FFT 的针对于一般的整系数多项式 的乘法。但是，大整数乘法中所要用到的多项式乘法十分特殊：即两个因子多 项式中，每一个系数都不大于 10. 因此下面所要找的， 就是对于这样一种特 殊的整系数多项式的比较合适的乘法算法。 我们的工具是模-p 的有限域。首先，如果我们在模-p 的有限域上能够计算 出： pxBxAxCmod即有，又根据多项式乘法可以知道，220 ,modnipccii，因此如果我们挑选一个足1818199, 1,0, 1

5、,0, 1,0 nbacikjnkjikjnkjikjnkjkji够大的 p 使得，则可知，又有：,，从而181nppcipci pcciimod可知.iicc 3.3 关于 p 的选择于是我们现在需要做的就是对于给定的一个数 p，设计一个类似于 FFT 的算法，求出。我们可以将 p 的取值范围缩小一点，针 pxBxAxCmod对于 p 为素数，且 p 足够大（显然要大于 2n-2）的情况来讨论。 这个任务其实就是要证明在模-p 的域上的“n 次单位根”具有与复数域上 的 n 次单位根类似的性质。即证明模-p 的域上的 FFT 算法是合法的。 【定理 1】模-p 乘法群是 p-1 阶循环群。【

6、证明】此定理等价于同余方程有 p-1 次本原单位根。这个定理pxpmod11的证明可以参考数论概论中关于模-p 的本原根的内容。在一般的近世代数 教材中也会有这一内容。由此，记 m=p-1,于是可以找到一个次单位根。由于 pn,所以 m=p-1n.从而 A（x）和 B（x）都可以表示成 m-1 次多项式。 011 1aaaAm m L将此分成两部分： xA 2 22 1 1122 12 122 2xxAxAxaxxaxAmkkk mkkk 于是， 2 22 1xxAxAxA 2 22 1xxAxAxA由上式可知，要计算和，只需要先计算和，然后再做一 xAxA 2 1xA 2 2xA次乘法、一次

7、加法和一次减法即可，要计算 k 个自变量的函数，需要的时间是：， 12/2kkTkT从而可得。 mmOmTlog由上面的式子可以看出，要想进行 FFT 变换，其关键在于对于 n 个自变量m,.,2求它们的函数的问题可以转化为求m,.,42对于另外一些多项式的函数问题。但是问题是在进行逆变换时必须要满足，根据等比数列公pmkkmod01 式，这样必有，也就是说，必须找到 n 次单pmmkkmod0111 1m位根。根据群论中的 Lagrange 定理，m|p-1，从而 p-1 必须精心选择，使得它 包含较多的素因子 2. 事实上，必须满足两个条件：折半引理和求和引理。求和引理已经在上一段描述过了

8、。折半引理指的是。因为只有这样我们才能够实施分imi2/治策略。 网络上有一种算法，是直接找出一个符合条件的大的素数 p。这种方法有 不完美之处：当 n 变得很大，超出了 p 的范围时，该算法就不适用了。当然， 这种方法已经能够满足现实中的大部分需求了。而且由于是事先计算好的模-p 的域，因而节省了大量的工作，其时间性能比较好。 我们的目的是寻找一种好的方法，使得该算法能够更容易地扩展，以适应 任何长度的大整数。关于 p 为素数的情况，现在貌似也找不到一种好的方法来。对于合数的情况，参见基于快速傅立叶变换的大整数乘法研究这篇论 文。虽然其定理十分优美，但是没有实用性。因为它所选取的合数 c 对 n 成指数级。即。这样在做运算的时候就失去了大整数乘法的时间优势，相12 nc当于白费力。