数论变换原理简述

liangbch

　楼上说，a可取2的方冪，这与apfloat不一致，apfloat说，a必须是质数模的一个原根，而且apfloat给出的3个原根，没有一个是2的方冪。

无心人

别插楼好不好啊

：（

apfloat只是实现的一种NTT，不要事事都看apfloat，俺摘录的可是国内最经典的数论变换的书上的内容啊
$\alpha$可以是任何值的，只要$M, N, \alpha$满足数论变换条件的

上面有数论变换成立条件的定理

而且$\alpha$并不是原根，它叫$N$阶本源单位根，我没把书上的数论基础知识帖上，具体看数论书。

liangbch

我们不是为了使用数论变换而使用数论变换，我所关心的是 怎样利用数论变换实现大数乘法（高效的大数乘法），纯理论性的东西没有多大意义。毕竟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$的绝对最小剩余，就能得到卷积的真值。

无心人

获得了可以任意修改帖子的权利
可以任意编辑了

这个东西放了很长时间了

下面我想先写出数论变换在大数乘法里的用处

然后讨论对大数乘法有用处的数论变换

比如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$，这里不再给出。

t	N	理论上 b位数	理论最大 乘法长度	双字b 长度	字节b 长度	双字变换 总长度
7	256	60	7680	1	7	128
8	512	124	31744	3	15	768
9	1024	251	128512	7	31	3584
10	2048	507	519168	15	63	15360
11	4096	1018	2084864	31	127	63488
12	8192	2042	8364032	63	255	258048
13	16384	4089	33497088	127	511	1040384
14	32768	8185	134103040	255	1023	4177920
15	65536	16376	536608768	511	2047	16744448
16	131072	32760	2146959360	1023	4095	67043328
17	262144	65527	8588754944	2047	8191	268304384
18	524288	131063	34357379072	4095	16383	1073479680
19	1048576	232134	137433710592	8191	32767	4294443008
20	2097152	524278	549745328128	16383	65535	17178820608
21	4194304	1048565	2199000186880	32767	131071	68717379584
22	8388608	2097141	8796046884864	65535	262143	274873712640
23	16777216	4194292	35184271425536	131071	524287	1099503239168
24	33554432	8388596	140737287028736	262143	1048575	4398029733 888
25	67108864	16777203	562949517213696	524287	2097151	17592152489984
26	134217728	33554419	2251798941270016	1048575	4194303	70368677068800
27	268435456	67108850	9007197375692800	2097151	8388607	281474842492928
28	536870912	134217714	36028793260867584	4194303	16777215	1125899638407168
29	536870912	268435441	144115180022792192	8388607	33554431	4503599090499 584
30	2147483648	536870897	576460736197296128	16777215	67108863	18014397435740160
31	4294967296	1073741808	2305842974853955584	33554431	134217727	72057591890444288
32	8589934592	2147483632	9223371968135299072	67108863	268435455	288230371856744448

可以看到使用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=
的过程中，无意也刚好搜到了这里，希望谁能简单地介绍下变换