数论变换由于快速傅里叶变换的提出，大大减少了计算运算次数，乘法与加法次数是由原来的 （ ）减为 （ ），可见大大节省计算量。在有循环卷积特性的条件下，快速数论变换是具有比快速傅里叶更快的快速变换算法。本文对快速数论变换算法进行了严格的推导。

按数论，一个集合或数系ZM={0，1，…，M-1}，对其元素作加法或乘法运算时，若其结果仍属于集合中的某一元索，则该数系定义为数环或称ZM，它是以M为模的整数环。当M为素数（一个大于1的整数，只能被1和它本身整除，如3，5，7，11等）则称ZM为数域。数论变换就是定义在整数的有限环和有限域内具有和DFT相似的结构形式。对一个有限长度N的整数序列x(n)，其数论变换定义为t图1.

式中x(n)，X(k)包含在有限集合的整数环ZM里，即x(n)，X(k)∈ZM，ZM={0，1，…，M…1}，α是与模M(mod M)有关的参数，所以式①、②是以M为模的同余运算。设给定一个固定的正整数M，把它叫做模，如果用M去除任意两个整数a与b，所得余数相同，则称 a和b对模M同余，并记作a=b（mod M)或b=a（mod M)。如 2≡5(mod 3)，5≡8(mod 3)则 2≡8(mod 3)。所以整数a和b对模M同余的充分必要条件是M能整除(a-b)。它等价a=b+Mq，q为整数。对一个固定的b值，有无穷多个a值与b值对模M同余。例如，如果知道某月的2日是星期日，则9，16，23，30都是星期日，因为它们对模7都是同余，即9≡2(mod 7)，16≡2 (mod 7)，……，同余运算有一定的规则。由于DFT是在复数域上具有循环卷积特性（CCP)的唯一变换形式，而NTT是在整数域上具有CCP的变换形式，因此对式①、②只要恰当地选取参数N．M和α，就可通过NTT在整数环上进行循环卷积运算。一般变换长度N的选择最好是2的幂或高度复合数(一个正整数除了能被1和它本身整除外，还能被另外的正整数整除），以便采用快速傅里叶变换(FFT)的各种快速算法。α的选择可直接取2或2的幂，这样与α相乘的运算就可以简化为移位操作了。模M的选择常用的有默森(Mersenne)数Mp=2-1(p为素数）和费玛（Fermat)数Ft=2+1(b=2，t=1，2，3，…）。所以有默森数变换（MNT）和费玛数变换(FNT)。前者无快速算法，后者有快速算法。分析表明，利用FNT的快速算法计算N点循环卷积只需作2Nlog2N次移位操作和2Nlog2N次加法，对于N≤256，比FFT提高速度约3~5倍，而且由于所有运算为取模的同余运算，因此求得的值无舍入误差。这些优点使NTT的硬件易于实现，但由于数论变换不具有通常谱的物理含义，因而仅适用于计算快速卷积，同时FNT变换长度N还与字长b成正比，使得长度N的增加受到一定限制。

在快速傅里叶变换(FFT)中,变换因子是一个复数，因而需要进行复数运算。但是，,这表明WN是1的N次根。对于任意整数k,是按k对N取模呈现周期性。在数论变换中,是以整数a代替复数WN实现正变换和反变换，要求这个整数是1的N次根。这一要求在一般的整数运算规则中不成立，只有采用同余式的运算规则才能找到满足这一要求的a和N。利用这样的a和N可以构成数论变换公式。

显然，这种变换在计算速度上比快速傅里叶变换快。

把一个给定的正整数M称为模(mod),如果用M去除任意两个整数α和β，所得余数相同,便称作α和β对模M同余，记作

α余β(modM)　 (2)

因此，同余式运算规则是以正整数M为模的整数环（域上所定义的一种线性正交变换。

在式(1)中,整数a、N、M三者之间必须满足如下关系：

aN呏1(modM)　 (3)

满足上式的最小正整数N叫做a对模M的指数，a是1的N次根，或简称a是N阶的。例如,a为2时对模7的指数是3，对模11的指数是10。

在数论变换中要求找到合适的a、N和M值。所选择的N应当是高复合数。但如采用2的乘方,就能构成像FFT算法那样的信号流图，并且希望选取的N值足够大,以满足实际需要。其次,所选取的a应当能用简便的方法实现乘法运算，因为在计算机中乘法运算最花费时间；如果a是2的乘方，可以用移位操作实现a的乘方运算,因而比较方便。又由于是模运算，所以不存在舍入误差。此外，M最好也是位数不太多的二进制数,而且必须是大于2的素数。

梅森数论变换　在数论变换的一般公式 (1)中的模M采用梅森数时，就称为梅森数论变换。麦森数为

M=2k－1　 (4)

它是一奇数。令k=PQ，P为素数，便有在此情况下，最大可能的变换长度决定于（2P-1）。以(2P－1)为模，可以找到

①　a=2,N=P,aN=2P呏1【mod(2P－1)】,但P是素数，N=P也是素数，不是高复合数。

②　a=－2，N=2P，(－2)呏1【mod(2P－1)】,但由于N=2P，故不是高的复合数。因此，取梅森数作模是不合适的。

费马数论变换　在数论变换中比较合理的模M是选用费马数，即

Ft=2b+1　b=2t　 (5)

前几个Ft的值是F0=3;F1=5;F2=17;F3=257；F4=65537；这五个费马数都是素数，而F5和F6都是复合数：

F5=4294967297=641×6700417

F6=274177×67280421310721在t>4的情况下，还没有发现一个费马数是素数。Ft称为第t个费马数，模Ft的计算可用b位算术运算来完成。信号所占用的位数和滤波器系数决定了在输出中不引起溢出误差所需用的b值，实际用的b值比信号所占用位数的两倍稍大。为了能够采用费马数，如果以溢出条件得到的b值不是一个2的幂时,应该把它增加到接近的2的幂数。

因为是按模M=Ft费马数进行算术运算，所以长为N=2m的序数的费马数论变换及其反变换表达式可写成其中N是满足此式的最小正整数。

费马数论变换和傅里叶变换相类似。当N=2m时,数论变换的快速计算法的信号流图和 FFT的算法信号流图也是一致的，只是把WN换成a。但是,费马数论变换的基本函数是由2的方幂构成，不需要使用乘法,仅为移位操作，其运算速度快于 FFT算法。加上费马数论变换算法是模算术运算，不存在舍入误差，从而能得到高精度的褶积。此外，由于FFT的基本函数是三角函数,需要预先存储这些基本函数，而费马数论变换算法却不需要存储基本函数。费马数论变换的缺点主要是它没有物理意义，在信号处理中不能运用中间过程；运算需要的字长与变换点数之间存在着严格的关系，随着输入序列的增长往往需要很长的字长。