數論變換由於快速傅立葉變換的提出，大大減少了計算運算次數，乘法與加法次數是由原來的 （ ）減為 （ ），可見大大節省計算量。在有循環卷積特性的條件下，快速數論變換是具有比快速傅立葉更快的快速變換算法。本文對快速數論變換算法進行了嚴格的推導。
好 處大大減少了計算運算次數條 件有循環卷積特性的條件下套用學科通信
基本介紹
- 中文名：數論變換
- 外文名：Number Theoretic Transforms
- 簡稱：NTT
- 好處：大大減少了計算運算次數條
- 條件：有循環卷積特性的條件下
- 套用學科：通信、信息
- 人物：傅立葉
按數論，一個集合或數系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的增加受到一定限制。
