数论变换原理简述

无心人

我想把数论变换的相关知识写下来
因为内容比较多，可能要拉很长的战线
用很长的时间，如果最后大家看不到很多的东西
只能说抱歉了，有知道的比我多的欢迎补充
内容多来自网络，自己也懒得写字了
为了防止犯前两天的错误，我会小量多次发，以保证质量

一、卷积
(该部分摘自http://class.htu.cn/SZBJ/6/6_40.htm)
    假设$x(t)$和$h(t)$是定义在实轴上的实值或复值函数，则$x(t)$与$h(t)$的卷积简记为$x(t)**h(t)$，且由以下积分确定

      $x(t)**h(t) = \int_{-\infty}^{\infty} x(\tau)**h(t - \tau)d\tau$  (11)

    这里的运算符“$**$”是一个抽象的数学符号。利用变量代换，不难发现“$**$”是可交换的，即

      $x(t)**h(t)=h(t)**x(t)$  (12)            

    因为卷积的原理特别不易想象，让我们用图作一简单解释。

数论变换原理简述

    图中(a)和(b)分别给出了函数$x(t)$和$h(t)$。在进行积分前必须形成$h(t-\tau)$，图中(c)和(d)两图显示了这一过程。可以看出这些运算都有很简单，首先绕原点折叠$h(\tau)$给出$h(-\tau)$，再将这个函数平移$t$。然后，对任意给定的$t$值，将$x(\tau)$与 $h(t-\tau)$相乘，并从负无穷到正无穷对乘积积分，$x(\tau)$与 $h(t-\tau)$的积是图6中(e)的阴影部分。于是，我们有

       $x(t)**h(t) = {(t/2, 0<=t<=1), (1-t/2, 1<= t <= 2), (0, other) :}$   (13)

结果如图中的(f)所示。

    在现代科学分析领域，也许最重要和最强有力的工具就是卷积与傅立叶积分之间的关系，它允许从空域的一个抽象运算转换成频域的一个简单数学乘法。换句话说，如果$x(t)$和$h(t)$的傅立叶变换分别是$X(f)$和H(f)，则$x(t)**h(t)$的傅立叶变换就是$X(f)$和$H(f)$的乘积，即

       $x(t)**h(t) \harr X(f)H(f)$  (14)

无心人

二、离散卷积
(摘录地址同上)
    假设${x(k)}$和${h(k)}$是以N为周期的周期点列，即$x(k)$和$h(k)$满足：
   
       $x(k+rN)=x(k), h(k+rN)=h(k), r=+-1, +-2, +-3, ... $  (21)

    则$x(k)$和$h(k)$的离散卷积定义为

     $x(k)**h(k)=\sum_{j=0}^{N-1}x(j)h(k-j), k=0, 1, ..., N-1$ (22)

    自然我们希望，由上式定义的离散卷积也有与与连续卷积相类似的性质，答案是肯定的，我们可以得到如下的关系式：

          $x(k)**h(k) \harr X(n)H(n)$    (23)                          

    于是上式把一较复杂的数学运算转化为一简单的乘法运算。

     这正表明了两个周期序列离散卷积的傅立叶变换等于其相应的两个离散傅立叶变换的积。类似地，如果定义
   
        $x(n)**h(n)=\sum_{j=0}^{N-1}x(j)h(n-j), n=0, 1, ..., N-1$ (24)

    我们还可以得到

        $x(k)h(k) \harr \frac {X(n)**H(n)}{N}$    (25)

    （23）式和（25）式统称为离散卷积定理。利用离散卷积定理，我们可以方便地获得如下的帕塞瓦尔等式
   
        $\sum_{k=0}^{N-1}h^2(k) = 1/N \sum_{n=0}^{N-1} |h(n)|^2$  (26)

无心人

三、离散卷积的计算

    直接利用（22）式做数值计算总共需要\( N（N-1）\)个加法和\( N^2 \)个乘法。然而我们可以把（65）式分解为如下3步来做。

    1．计算$x(k)$ 和$h(k)$的离散傅立叶变换

    ${(X(n) = \sum_{k=0}^{N-1}x(k)e^{-2\pi i nk//N} ), (H(n) = \sum_{k=0}^{N-1}h(k)e^{-2\pi i nk//N}) :}$     (31)

    2．计算 $Y(n)=X(n)H(n)$。

    3．计算逆傅立叶变换：

    $ Y(k) = \frac{1}{N} \sum_{n=0}^{N-1}Y(n)e^{2\pi i nk//N}$   (32)

    如果引进记号$Y^**(n)$表示$Y(n)$的复共轭，则

     $Y(n)e^{2\pi i nk//N} = (Y^**(n)e^{-2\pi i nk//N))^**$   (33)
   
    于是（32）式可改写为
   
    $Y(k) = [sum_{n=0}^{N-1} (\frac{1}{N} Y^**(n)) e^{-2\pi i nk//N}]^**$  (34)

    则（34）式中的中括号部分恰是一个傅立叶变换。

    于是简单的离散卷积公式（22）可以被上述三步所取代。这样做似乎走了许多弯路，但由于FFT的高效性，用上述三步可以有效地降低计算量，并且问题的规模越大，降低的倍数越多。

通常意义上的卷积到此为止，
至于FFT的具体算法有时间另外开帖。
下面转入数论变换意义下的卷积

无心人

四、循环卷积
由此开始的定义叙述和上面的就可能稍微有点不同了（但结果是一致的），请注意

    设两个长为$N$的序列$x_n$和$h_n$, $n = 0, 1, ..., N-1$

    其卷积是指

    $y_n = \sum_{k=0}^{N-1} x_kh_{n-k} = \sum_{k=0}^{N-1} x_{n-k}h_k$  (41)

    其中假定$x_n = h_n = 0, n < 0$。

    （41）的矩阵表示是：
   
    $[(y_0), (y_1), (y_2),  ..., (y_{N-1})] = [(h_0, 0, 0, ..., 0), (h_1, h_0, 0, ..., 0), (h_2, h_1, h_0, ..., 0), (... , ..., ..., ..., 0), (h_{N-1}, h_{N-2}, h_{N-3}, ...  ,h_0)] \quad [(x_0), (x_1), (x_2), (...), (x_{N-1})]$   (41')

    直接计算（41）大约需要$N^2$次乘法和$N^2$次加法，当N很大时其计算工作量是很大的，因此寻求快速算法以节约时间是一个很有意义的工作。

    通常通过循环卷积来计算（41），所谓两个序列$N$的$x_n$和$h_n$, $n = 0, 1, ..., N-1$的循环卷积是指：

    $y_n = \sum_{k=0}^{N-1} x_kh_{<n-k>_N} = \sum_{k=0}^{N-1} x_{<n-k>_N}h_k$  (42)
      $(n = 0, 1, ..., N-1)$

    或者用矩阵表示

    $[(y_0), (y_1), (y_2), ..., (y_{N-1})] = [(h_0, h_{N-1}, h_{N-2}, ..., h_1), (h_1, h_0, h_{N-1}, ..., h_2), (h_2, h_1, h_0, ..., h_3), (... , ..., ..., ..., ...), (h_{N-1}, h_{N-2}, h_{N-3}, ...  ,h_0)] \quad [(x_0), (x_1), (x_2), (...), (x_{N-1})]$   (42')

      $<k>_N$表示$k$对$N$的最小非负剩余。
       例如：

       $<7>_4 = 3, <-7>_4 = 1$

     下面的引理说明如何用循环卷积来计算卷积
      
      引理1  两个长为$N$的序列$x_n$和$h_n$的卷积可以用两个长为$2N$的序列$\hat x_n, (n = 0, 1, ..., 2N-1)$和$\hat h_n, (n = 0, 1, ..., 2N-1)$的循环卷积来计算：
      设：
      
      $hat x_n = { (x_n, (n = 0, 1, ..., N-1)), (0, (N <= n <= 2N-1)) :}$

     $hat h_n = { (h_n, (n = 0, 1, ..., N-1)), (0, (N <= n <= 2N-1)) :}$

    $\hat x_n$和$\hat h_n$的循环卷积记为$\hat y_n$
   
      $\hat y_n = \sum_{n=0}^{2N-1} \hat x_k \hat h_{<n-k>_{2N}}$

    则$y_n = \hat y_n, (n= 0, 1, ..., N-1)$
   
*************************************************************************
    通常要进行卷积运算的两个序列的长度是不同的。
   
    $x_n, n = 0, 1, ..., M_1 - 1, h_n, n = 0, 1, ..., M_2 - 1$
   
    此时的离散卷积
   
    $y_n = \sum_{n=0}^{M_1-1} x_kh_{n-k}=\sum_{n=0}^{M_2-1}x_{n-k}h_k$
   $n = 0, 1, ..., M_1+M_2 - 2; x_n = h_n = 0,n<0$

    这种卷积可以补零变成长度相同($M_1+M_2-2$)的卷积。输出序列$y_n$的长度亦为$M_1+M_2-2$。
   
    例如：

    $x_n, (n=0,1), h_n, (n=0, 1, 2, 3)$
   
   $[(y_0), (y_1), (Y_2), (y_3)] = [(h_0, 0), (h_1, h_0), (h_2, h_1), (h_3, h_2)] \quad [(x_0), (x_1)]$  (a)

   对序列$x_n$, $h_n$补零成为长度均为4的序列, $(x_0, x_1, 0, 0), (h_0, h_1, h_2, h_3)$做他们的如下卷积：
   
    $[(y_0), (y_1), (Y_2), (y_3)] = [(h_0, 0, 0, 0), (h_1, h_0, 0, 0), (h_2, h_1, h_0, 0), (h_3, h_2, h_1, h_0)] \quad  [(x_0), (x_1), (0), (0)]$  (b)
   
   由计算知道(a)和(b)的结果是相同的。
   
   所以我们以后可只考虑长度相同的离散卷积。
*************************************************************************

无心人

五、离散傅立叶变换的结构
接三楼考虑下离散傅立叶变换

考虑（31）（32）的另外一种表示，

定义

$W_N = e^{- 2 \pi i // N }$

则（31）可表示为

${ (x_n = \sum_{k=0}^{N-1} x_k W_N^{nk}), (h_n = \sum_{k=0}^{N-1} h_k W_N^{nk}) :}$ (51)

(32)可表示为

$y_k = 1 / n \sum_{n=0}^{N-1} y_n W_N^{-nk}$ (52)

考虑他们的矩阵形式
定义：

$T_N = [(1, 1, 1, ..., 1), (1, W_N, W_N^2, ..., W_N^{N-1}), (1, W_N^2, W_N^4, ..., W_N^{2(N-1)}), (\vdots, \vdots, \vdots, \vdots, \vdots), (1, W_N^{N-1}, W_N^{2(N-1)}, ..., W_N^{(N-1)^2})]$

$T_N^{-1} = [(1, 1, 1, ..., 1), (1, W_N^{-1}, W_N^{-2}, ..., W_N^{-(N-1)}), (1, W_N^{-2}, W_N^{-4}, ..., W_N^{-2(N-1)}), (\vdots, \vdots, \vdots, \vdots, \vdots), (1, W_N^{-(N-1)}, W_N^{-2(N-1)}, ..., W_N^{-(N-1)^2})]$

则（51），（52）可写作

    $ (X) = T_N(x), (H) = T_N(h)$

    $ (y) = T_N^{-1}(Y)$

    其中

    $(x) = [(x_0), (x_1), (x_2), (\vdots), (x_{N-1})]  \quad (h) = [(h_0), (h_1), (h_2), (\vdots), (h_{N-1})]$
   
    $(X) = [(X_0), (X_1), (X_2), (\vdots), (X_{N-1})]  \quad (H) = [(H_0), (H_1), (H_2), (\vdots), (H_{N-1})]$

    $(Y) = [(Y_0), (Y_1), (Y_2), (\vdots), (Y_{N-1})] = [(X_0H_0), (X_1H_1), (X_2H_2), (\vdots), (X_{N-1}H_{N-1})] \quad  (y) = [(y_0), (y_1), (y_2), (\vdots), (y_{N-1})] $

    存在快速算法计算DFT，称为快速傅立叶变换(FFT)。

    但由于FFT中存在浮点运算，有速度慢精度低的缺点，在数论中，又发展了一类以整数运算为基础的计算卷积的方法，称为数论变换(NTT)，特别是其中的Fermat变换(FNT)仅使用加减和移位运算，是目前最快速的算法。

无心人

六、具有循环卷积性质的变换结构

    考虑线性非奇异变换$T$，其元素记为$T_{k,m}, (k, m = 0, 1, 2, ..., N-1)$

    $T = [(t_{0,0}, t_{0,1}, t_{0,2}, ..., t_{0, N-1}), (t_{1,0}, t_{1,1}, t_{1,2}, ..., t_{1, N-1}), (t_{2,0}, t_{2,1}, t_{2,2}, ..., t_{2, N-1}), (\vdots, \vdots, \vdots, \vdots, \vdots), (t_{N-1,0}, t_{N-1,1}, t_{N-1,2}, ..., t_{N-1, N-1})]$    (61)

    记序列$x_n, h_n$的变换各为$X_k, H_k$，$x_n, h_n$的循环卷积$y_n$的变换为$Y_k$。

    $X = T(x)$
   
    $H = T(h)$          (62)
   
    $Y = T(y)$

    如果变换具有如下性质：
   
     $Y_k = X_k * H_k \quad (k = 0, 1, ..., N-1)$   (63)

    则称$T$为具有循环卷积性质的变换。

     变换具有循环卷积性质的充分必要条件是：
   
     $t_{k, m} = \alpha^{km}, \quad (k, m = 0, 1, 2, ..., N-1)$  (64)

    其中$\alpha$为$N$阶单位根，也就是说$T$具有下列形式。

     $T = [(1, 1, 1, ..., 1), (1, \alpha, \alpha^2, ..., \alpha^{N-1}), (1, \alpha^2, \alpha^4, ..., \alpha^{2(N-1)}), (\vdots, \vdots, \vdots, \vdots, \vdots), (1, \alpha^{N-1}, \alpha^{2(N-1)}, ..., \alpha^{(N-1)^2})]$   (65)

    具有（65）结构的变换是可逆的。定义
     以
      $\hat t_{k, m} = N^{-1} \alpha^{-km} \quad (k, m = 0, 1, 2..., N-1)$
    为元素的矩阵$U$是$T$的逆矩阵，即$TU = UT = I$，其中$I$为单位矩阵。

    容易证明：
    1、复数域上仅有DFT是唯一的具有循环卷积性质的变换。
    2、具有（65）形式的变换是正交变换。

    在$ZZ_m$上，$\alpha$只要满足一定条件，变换$T$仍然具有循环卷积性质，而且可逆，$T^{-1} = U$，这个正是下面要讲到的数论变换。

无心人

七、一维数论变换
终于说到了数论变换

    现在在以正整数$M$为模的整数环（或者域）$ZZ_M$上具体建立具有循环卷积性质的可逆变换。

    在$ZZ_M$上给出两个长为$N$的序列$x_n$和$h_n$和其循环卷积$y_n$。

     $(x) = [(x_0), (x_1), (x_2), (\vdots), (x_{N-1})], \quad (h) = [(h_0), (h_1), (h_2), (\vdots), (h_{N-1})]  $

    $y_n = \sum_{k = 0}^{N-1} x_kh_{<n-k>_N} \quad (n = 0, 1, 2, ..., N-1)$

    考虑可逆变换$T$，做变换：

     $X -= T(x) \quad (mod M)$
   
    $H -= T(h) \quad (mod M)$

    $Y -= T(y) \quad (mod M)$

    完全同上节的讨论，欲使$T$具有循环卷积性质：
     
     $Y_k = X_k H_k \quad (mod M), \quad (k = 0, 1, 2, ..., N-1)$

    只要$T$具有如下结构：

      $T = [(1, 1, 1, ..., 1), (1, \alpha, \alpha^2, ..., \alpha^{N-1}), (1, \alpha^2, \alpha^4, ..., \alpha^{2(N-1)}), (\vdots, \vdots, \vdots, \vdots, \vdots), (1, \alpha^{N-1}, \alpha^{2(N-1)}, ..., \alpha^{(N-1)^2})] \quad (mod M)$

    其中$\alpha$为模$M$的$N$阶本原单位根。

    当$M = p_1^{l_1}*p_2^{l_2}*...*p_s^{l_s}$时，$\alpha$不仅对模$M$的阶为$N$，且模所有$p_i, (i=1, 2, ..., s)$的阶为$N$时，下列的一对变换互为逆变换。
    设$x_n in ZZ_m, \quad (n=0, 1, 2, N-1)$则称

      $X_k -= \sum_{n=0}^{N-1}x_n\alpha^{nk} \quad (mod M) \quad (k=0, 1, 2, ..., N-1)$   (71)

      $x_n -= N^(-1) \sum_{k=0}^{N-1}X_k\alpha^{-nk} \quad (mod M)\quad (n=0, 1, 2, ..., N-1)$   (72)

    为数论变换（NTT），其中$\alpha in ZZ_m, \quad N >= 2$。

    下面不加证明，写出一些关于NTT存在的定理。具体证明见相关书籍。

    定理1   设$M = p_1^{l_1}*p_2^{l_2}*...*p_s^{l_s}$， 当且仅当
    1、$N^{-1}$在$ZZ_M$上存在，即$(N, M) = 1$；
    2、$\alpha$对模$M$是$N$阶本原单位根；
    3、$\alpha$对模$p_i, (i=1, 2, ..., s)$的阶亦为$N$时；
    （71）（72）互为逆变换。

    定理2   设$M = p_1^{l_1}*p_2^{l_2}*...*p_s^{l_s}$， 当且仅当
    1、$N^{-1}$在$ZZ_M$上存在，即$(N, M) = 1$；
    2、$\alpha$对模$p_i^{l_i}, (i=1, 2, ..., s)$的阶亦为$N$时；
    （71）（72）互为逆变换。
   
    定理3  设$M$为任一自然数，当且仅当
    1、$N^{-1}$在$ZZ_M$上存在，即$(N, M) = 1$；
    2、$\alpha$对模$M$是$N$阶本原单位根；
    3、在$ZZ_M$上存在$\beta_j, (j = 1, 2, ..., N-1)$使
      $\beta_j(\alpha^j - 1) -= 1 \quad (mod M) \quad (j = 1, 2, ..., N-1)$
   时（71）（72）互为逆变换。

    定理4   设$M = p_1^{l_1}*p_2^{l_2}*...*p_s^{l_s}$， 当且仅当
      $N | O(M) = (p_1 - 1, p_2 - 1, ..., p_s - 1)$
   时（71）（72）互为逆变换。其中
        $O(M) = (p_1 - 1, p_2 - 1, ..., p_s - 1)$
   表示$p_1 - 1, p_2 - 1, ..., p_s - 1$的最大公约数。

    定理5  在定理1~4条件下，变换（71）（72）具有循环卷积性质。
   
    推论  在以正整数$M$为模的正整数环$ZZ_M$上，具有循环卷积性质的变换的最大长度
        $N_max = O(M)$。

    定理4极为重要，它使我们能对给定的正整数$M$具体选定变换的长度$N$从而确定$\alpha$以构成数论变换(NTT)。

无心人

八、数论变换具体参数选择
   
    一般情况下，当$N = 2^t$时，数论变换存在快速算法，当$\alpha=2^b$为时数论变换的计算最简单，只需要加减法和移位，当M的二进制表示最简单时，模$M$的运算最简单。
   
    那么如何寻找最好的参数呢？
   
    三个参数决定了一个数论变换，即$M, N, \alpha$，当然，这三个参数是相互关联的。
   
    那如何决定一个具体的数论变换的参数呢？
   
问题一，给定$M, N$如何确定$\alpha$

    由上面的叙述，假定$M = p_1^{l_1}p_2^{l_2}..p_s^{l_s}$，则$N | O(M)$。

    根据上面的定理，$\alpha$必须同时是$M$和$p_i(i=1, 2, ..., s)$的N阶本源单位根。

    容易证明，共有$\varphi^s(N)$个$\alpha$适合我们的要求，其中任何的$\alpha$都能和$M, N$组成一个NTT。

    步骤一、对模$p_i$求出N阶本源单位根$\beta_i$。$p_i$为奇素数（若$M$包含因子$2$，则可证明其变换长度$N=1$是无意义的），在$ZZ_{p_i}$上存在原根$g_i$，取$\beta_i = g_i^{{p_i - 1}/N}$，则$\beta_i$即为所求。

   步骤二、对模$p_i^{l_s}$求出N阶本源单位根$\alpha_i$。令$\alpha_i = \beta_i^{p_i^{l_i - 1}}$，则$\alpha_i$即为所求。

   步骤三、对模$M$求出$N$阶本源单位根$\alpha$。由于第二步已求得模$p_i^{l_i}$的$N$阶本源单位根$\alpha_i$，用中国剩余定理，求联立方程：

    $\alpha -= \alpha_i  \quad (mod \quad p_i^{l_i}) \quad (i = 1, 2, ..., s)$
   
    的解，其解为$\alpha -= \sum_{i=1}^s M_i^' M_i \alpha_i \quad (mod M)$。其中$M_i^' M_i -= 1 \quad (mod \quad p_i^{l_i})$，此$\alpha$即为所求。

   你提到 M 应该选择合数，但是apfloat中用的模则是质数。 by liangbch

   M 可以是合数，也可以是素数。by 无心人

[ 本帖最后由 liangbch 于 2008-4-17 20:57 编辑 ]

无心人

例， 设$M = 5^2*13^2, N= 4$, 求$\alpha$
      第一步，求$\beta_1, \beta_2$
          容易求得, $\beta_1 = 2, 3;  \beta_2 = 5, 8$
          第一步也可查表获得。
       第二步，由$\alpha_i = \beta_i^{p_i^{l_i- 1}}$得到
           $\alpha_1 = 2^5 -= 7 (mod 5^2) \quad alpha_2 = 5^13 -= 70 (mod 13^2)$
           $\alpha_1 = 3^5 -= 18 (mod 5^2) \quad \alpha_2 = 6^13 -= 99 (mod 13^2)$
      第三步、从以下四组联立方程得到最后的$\alpha$

         ${(\alpha -= 7 (mod 5^2)), (\alpha -= 70 (mod 13^2)) :}$
         ${(\alpha -= 7 (mod 5^2)), (\alpha -= 99 (mod 13^2)) :}$
         ${(\alpha -= 18 (mod 5^2)), (\alpha -= 70 (mod 13^2)) :}$
         ${(\alpha -= 18 (mod 5^2)), (\alpha -= 99 (mod 13^2)) :}$
       应用中国剩余定理，求出四个$\alpha$如下：
          268, 1282, 2943, 3957
      这四个$\alpha$任一个和$M=5^2*13^2$及$N=4$均能组成NTT。

无心人

问题二、如何选择合适的$M, N, \alpha$。为了使NTT具有快速计算的特点，选择三个参数就成了构成快速NTT的关键，以下几点说明了如何选择一个合适的参数。
      
      1、变换长度$N$必须适合FFT类型的快速计算，即$N$必须是一个高度的复合数。特别是$N=2^m$时，可做出最快速简单的变换。但$N$也不能太小，否则可计算长度就很可能达不到要求。

      2、数论变换的一个特点是使用一个整数$\alpha$代替DFT中的$W_n = e^{-2 pi i // N}$，FFT需要大量的复数乘法，而NTT只需要做$\alpha$的方幂的乘法。如果选择合适的$\alpha$，使得乘$\alpha$的幂是一个简单的运算，则可以达到快速运算的目的。当$\alpha$的方幂二进制表示很小时，就能达到这样的目的。特别是如果$\alpha$是$2$的幂，则是最简单的情况，这时在二进制计算机上，乘以$\alpha$的方幂等于做移位运算。

      3、为了做模$M$运算，在其二进制表示里，$M$位数越小越好，但小的$M$可能会在计算中导致中间结果和最终结果的溢出。另外$M$的二进制表示如果简单的话，很可能模$M$运算只使用移位和加减法就能完成，比如$M=2^t +- 1$就是一个例子。

    一）对$M$的选择
    变换长度$N$和模$M$的关系是$N|O(M)$，因此

    1、当$M$是一个偶数时，$2$是$M$的一个因子，因此变换长度只能是$N=1$，这是没有意义的。因此，$M$不能是偶数。

    2、$M$是大于$2$的素数，此时$M$是一个奇数，因此$(2, M) = 1$，由Fermat定理
            
                 $2^{M-1} -= 1 (mod M)$
   
       因此$N$可取$M-1$的任一因子，$\alpha$是$2$的方幂, $N_{max} = M-1$。例如$M = 17, N | 16, N = 2, 4, 8$， 相应的$\alpha = 4, 2, sqrt(2)$。虽然$M$取奇素数时可以满足要求， 但此时N不一定是高度复合数，更未必有$2^m$形式。
   
    3、$M$取做Mersenne数。
    设$M = 2^k - 1, k > 1$。$M$为一个奇数。
   
    令$k = pq$，$p$是一个素数。

            $2^k - 1 = 2 ^{pq} - 1 = (2^p)^q - 1 -= 0 mod (2^p - 1)$

    所以$2^p - 1$是$2^k - 1$的一个因子，从而最大可能变换长度取决于$2^p - 1$。
     
    如果$M = 2^p - 1$， $p$是一个素数，这样的数称为Mersenne数，取Mersenne数做模是适合NTT要求的。以Mersenne数做模的数论变换叫Mersenne数变换，记做MNT，对于MNT， $\alpha = 2, N = p$或者$\alpha=-2, N = 2p$。
   
    4、$M$取做Fermat数。
    设$M = 2^k + 1, k > 1$。$M$也是一个奇数。

    设k为奇数，$k = 2t + 1$

      $2^k + 1 = 2^{2t+1} + 1 = (2 + 1)(2^{2t} - 2^{2t-1} + ... - 2 + 1) = 3(2^{2t} - 2^{2t-1} + ... - 2 + 1)$
     
    故$3|2^k + 1$，此时$N_[max} = 2$显然不符合要求。

    设$k = s2^t$，$s$为奇数， $t = 1, 2, ...$。
            
              $M = 2^{s2^t} + 1$

       $2^{s2^t} + 1 = (2^2^t)^s + 1 -= (-1)^s + 1 -= 0 (mod 2^2^t + 1)$
   
    即$2^26t + 1 | 2^{s2^t} + 1$，所以此时变换长度取决于$2^2^t + 1$。

     令$F_t = 2^2^t + 1, t = 0, 1, 2, ...$为模$M$。
            
           $M = 2^b + 1, b = 2^t, t = 0, 1, 2, ...$

     这样的数叫做Fermat数，以Fermat数做数论变换称为Fermat数变换，记做FNT。对于FNT，$N=2b, \alpha = 2$或者$N = 4b, \alpha = sqrt(2)$均能满足要求。