楼上说，a可取2的方冪，这与apfloat不一致，apfloat说，a必须是质数模的一个原根，而且apfloat给出的3个原根，没有一个是2的方冪。
别插楼好不好啊
：（
apfloat只是实现的一种NTT，不要事事都看apfloat，俺摘录的可是国内最经典的数论变换的书上的内容啊
$\alpha$可以是任何值的，只要$M, N, \alpha$满足数论变换条件的
上面有数论变换成立条件的定理
而且$\alpha$并不是原根，它叫$N$阶本源单位根，我没把书上的数论基础知识帖上，具体看数论书。
我们不是为了使用数论变换而使用数论变换，我所关心的是 怎样利用数论变换实现大数乘法（高效的大数乘法），纯理论性的东西没有多大意义。毕竟apfloat实现了一个使用数论变换的大数乘法，我们参考他的东西有何不对？
论坛就是讨论问题的，你也没说不许跟贴呀？如果你不想让我们跟贴，可事先声明。
:(
纯理论性的东西是为了确定如何定义一个数论变换啊
到目前为止的东西已完整的描述了如何定义，如何寻找，如何具体选择一个NTT
再加上下面一个帖子，就组成了一个完整的数论变换理论
理论缺少不了了
干巴巴的说，要什么参数，什么形式的NTT，谁知道为什么啊？
况且，我已经把理论给肢解到光剩骨头了
连骨头都没有可就不好玩了
感谢楼主在数论变换理论方面做出的大量工作。对数论变换，我并不大懂，主要知识来自apfloat。提问是为了学习，为了真理，而不是为难谁。
--liangbch
[ 本帖最后由 liangbch 于 2008-4-18 11:33 编辑 ]
二）$M$选择的另外一个考虑
（纯理论到这里应该就结束了）
如果我们利用NTT的循环卷积特性来计算数字序列循环卷积
$y_n = \sum_{k=0}^{N-1}x_kh_{<n-k>_N}, n = 0, 1, ..., N-1$
由于NTT所用的运算是模运算，这样求得的卷积值$y_n$是模$M$的同余值，即
$ \sum_{k=0}^{N-1}x_kh_{<n-k>_N} -= y_n (mod M)$
$y_n$所属的同余类中的每一个$y_n + rM$都是满足要求的，到底哪个才是我们要求的呢？我们可以通过选择$M$得到解决。
通常情况下, $|x_n|_{max}, |h_n|_{max}$ 都是确定的，那么如果选择$M$满足
$y_n <= min{|x_n|_{max} \sum_{k=0}^{N-1} |h_k|, |h_n|_{max} \sum_{k=0}^{N-1} |x_k|} <= M / 2, n = 0, 1, ..., N-1$
由于当$-M /2 < a < M / 2$时，$a = r_a$，其中$|r_a| < M / 2$，$r_a$为$a$模$M$的绝对最小剩余，因此在用NTT计算循环卷积时，由上面的不等式存在，只需在计算结果时取模$M$的绝对最小剩余，就能得到卷积的真值。
:lol
获得了可以任意修改帖子的权利
可以任意编辑了
这个东西放了很长时间了
下面我想先写出数论变换在大数乘法里的用处
然后讨论对大数乘法有用处的数论变换
比如MNT就不打算讨论了
九、数论变换在大数乘法里的应用
考虑两个$b$进制整数$u, v$
$u = u_mb^m + u_{m-1}b^{m-1} + ... + u_1b + u_0$
$v = v_nb^n + v_{m-1}b^{m-1} + ... + v_1b + v_0$
则称$u$为$m+1$位$b$进制数字，称$v$为$n+1$位$b$进制数字。
显然，$u, v$还可以表示成下列形式：
$u = \sum_{i=0}^{m} u_i b^i, \quad v = \sum_{i=0}^{n} v_i b^i$
那么$u, v$的乘积$y = uv$就可以表示成如下形式了：
$y = uv, \quad y = \sum_{k=0}^{m+n} y_k b^k, \quad y_k = \sum_{i=0}^{k} u_i*v_{k-i}$
其中$u_i = 0, (i > m) \quad v_i = 0 (i > n)$
$y_k$可能大于等于$b$，所以最后需要通过一个规格化过程来规范最后的结果。
显然，如果把$u, v, y$各位按照从最低位到最高位的排列看做一个序列的话，$y$就是$u, v$的一个卷积了。
就是说，大数乘法是可以通过卷积运算来进行的。
上面已经证明，不同长度的卷积是可以通过补零化为相同长度的卷积的，所以对于大数乘法，我们也只考虑相同长度（或者位数）的卷积算法。
容易证明，快速傅立叶变换（FFT）是可以用作大数乘法的，这里我们不做讨论。（某些特殊FFT算法甚至比NTT要有效率，但涉及浮点运算，所以整体下FFT不如NTT）
同样道理，我们也可以证明，NTT也具有做大数乘法卷积的能力，且只涉及整数运算，同样条件下，比FFT速度要快。
在NTT条件下，大数乘法卷积算法对$M, N, \alpha$是有一定限制的，在上面帖子里提到了如何选择$M, N, \alpha$，特别是如何保证最终结果正确且唯一，这里我们不再重复。
在大数乘法卷积意义下，因为参与运算的数均为非负数，我们需要修改下限定条件（如果还遵守先前的限定也可以，但可卷积的数字就受到更严格的限制）。
我们有如下大数乘法下卷积算法选择$M, N, \alpha$的一个限定条件
$N * (b-1)^2 < M$
另外，由于NTT是通过循环卷积来计算的，即高半序列均为0, 且通常实用的$N$为偶数
则条件可放宽为
$N // 2 * (b-1)^2 < M$
===============================================
说明下
大数乘法的进制$b$并不必须是当前的进制，就是说，你完全可以用很大的$b$值来划分数字以保证能充分的适合参数$M, N, \alpha$，一旦某些参数选择了大的$b$值，会导致中间过程的普通乘法出现大数运算，很可能导致中间结果的运算也符合NTT要求，即出现迭代的NTT算法，这也是可以的，而且对某些位数比较大的数字，使用两重甚至更多重NTT比单纯一重的NTT即能选择到合适的参数，也能提高运算的效率。
十、几个有用的数论变换
终于说到具体的了， BS我吧，啰啰嗦嗦
(一)费马数变换FNT
说到费马数变换FNT，不得不说，这个变换是整个NTT里实现最简单的变换，但存在着字长迅速膨胀的问题，所以目前无法代替其他变换。
费马数变换FNT是以参数$M = 2^b, b = 2^t$即费马数，为特征的变换。
因为至今只发现$t <= 4$下，费马数是素数，所以费马数变换可分成两类。下面不做证明给出：
1) $t <= 4$下，容易证明$N = 2^b, \alpha=3$构成NTT，该变换对大数运算并无多少益处，我们不再讨论。
2) 普通情况下，即$t$为任何值$N = 2b, \alpha=2$构成一个NTT，特别的如果$\alpha=sqrt(2)$，则$N=4b$也可构成一个NTT，这里我们只考虑$N = 2b, \alpha=2$情况。
考虑FNT变换$M = 2^b, b = 2^t, N = 2b, \alpha=2$，容易证明：
一个FNT用于大数乘法，则每次可计算的大数乘法的最大二进制长度为
$N // 2 * log_2 b = N // 2 * log_2 sqrt(2M // N) = 2^t * log_2 sqrt(2^{2^t} // 2^t) = 2^t * log_2 sqrt(2^{2^t - t}) = 2^t * (2^{t-1} - [(t +1)// 2])$
而此时的进制$b, log_2 b = 2^{t-1} - [(t+1)//2]$
考虑实际情况，序列的分割如果是以字节或者双字为单位则不会有额外的工作量，则一般要求$32 | log_2 b$， 即实际的序列每项二进制表示的长度是32的倍数，且
$2^{t-1} - [(t+1)//2] >= 32$
$t >= 7$
如果以字节做单位分割，则会比双字有更大的长度上限，但考虑目前32位CPU处理字节会涉及到对齐操作，可能会有额外的开销，所以是否可行必须通过测试得到结论。
这样子就有下列的FNT乘法的实际数据的表格了。
$t$是参数$M = 2^b, b = 2^t$中的$t$, $N=2b$,理论上b位数，是按照上面公式算出的在$N$变换长度下，每项的最大二进制长度。理论上乘法最大长度是按照理论上b位数长度乘以$N/2$得到的（记住高半序列填充0）。双字b长度、字节b长度分别是换算到双字和字节后的结果，双字变换总长度是换算成双字长度后，再乘以$N/2$的结果，是以双字为基本单位计算出的大数乘法可以变换的双字最大长度，应该还有一个字节变换总长度，等于字节b长度乘以$N/2$，这里不再给出。
tN理论上
b位数
理论最大
乘法长度
双字b
长度
字节b
长度
双字变换
总长度
725660768017128851212431744315768910242511285127313584102048507519168156315360114096101820848643112763488128192204283640326325525804813163844089334970881275111040384143276881851341030402551023417792015655361637653660876851120471674444816131072327602146959360102340956704332817262144655278588754944204781912683043841852428813106334357379072409516383107347968019104857623213413743371059281913276742944430082020971525242785497453281281638365535171788206082141943041048565219900018688032767131071687173795842283886082097141879604688486465535262143274873712640231677721641942923518427142553613107152428710995032391682433554432838859614073728702873626214310485754398029733
888256710886416777203562949517213696524287209715117592152489984261342177283355441922517989412700161048575419430370368677068800272684354566710885090071973756928002097151838860728147484249292828536870912134217714360287932608675844194303167772151125899638407168295368709122684354411441151800227921928388607335544314503599090499
5843021474836485368708975764607361972961281677721567108863180143974357401603142949672961073741808230584297485395558433554431134217727720575918904442883285899345922147483632922337196813529907267108863268435455288230371856744448
可以看到使用FNT变换计算乘法，可计算长度是大约以4倍增加的，所以在两个长度中间的乘法也许有其他更快速的NTT变换。当然，目前FNT是最快的，因为中间过程只有加减法和移位。
[ 本帖最后由 无心人 于 2008-5-7 10:20 编辑 ]
FNT中的一些问题
[ 本帖最后由 无心人 于 2008-5-7 10:33 编辑 ]
在解一个趣题 http://bbs.emath.ac.cn/viewthread.php?tid=1765&extra=
的过程中，无意也刚好搜到了这里，希望谁能简单地介绍下变换