关于实现中国剩余定理大规模运算的代价问题
假设中国剩余定理中同余式等式共有10000个,即有10000个 C = y_{i}\pmod r_{i},
r_{i}是20比特长的素数, 则计算C是不是可行的呢?
某个人说大量的计算使得最后得到C值不现实,因为最后算
C = (y_{1}*R_{1}*R '_{1} +...+ y_{10000}*R_{10000}*R '_{10000})MOD (R),
其中 R=r_{1}*...*r_{10000}, 而这个数R有10000*20位的比特长,这样的模运算不是很现实.
但后来,我查了一下, Aho等人写的那本算法分析与设计的书,里面有一个定理说时间复杂度可表示为20*10000比特长的两个数相乘的比特操作代价, 然而大比特数相乘,用分治法来做后, 20*10000比特长的数应该可以表示成3^(20)个两个32-比特数的乘法,还有其他一些加法和移位, 所以我想这个操作应该不是不很现实的吧.
不知道是不是正确. 看看哪位能帮助解答一下.
[解决办法]
10000*20个比特位？这才多大？
用二分分治的大整数乘法，复杂度是O(n^a)[a=log2(3)，以2为底3的对数,a约为1.585]。对于n=200000,这个算法耗时的确有点大。
大整数的乘法，最快的当然是FFT了，复杂度是O(nlogn)[n是乘数的长度]。
对于10000*20=200000个比特位的大整数相乘，FFT在一秒内出解，不是什么难事。
[解决办法]
我在想：为了计算两个大数的乘积，需要先一一求出乘数与被乘数关于这些模的剩余，而后还要进行大数的乘、加，最后也许还需要若干次的比较、减法等运算修正。你这么做是否划算？
[解决办法]
完全赞同medie2005的见解。你的算法是可行的，但是如果要算大整数的乘法，还是要用FFT。
[解决办法]
to qxqcn:
《计算机程序设计艺术》中就介绍了这样一个基于同余理论的大整数乘法，Knuth说那个算法的复杂度不是太大（具体的复杂度我不记得了）。
不过，Knuth介绍的那个算法，是经过特殊设计的，各个模很特殊，计算起来并不是很费劲。如果对于一般的模，效率应该不会很好。
