FFT和NTT的區別
快速傅里葉變換 (FFT) 和數論變換 (NTT) 之間的主要區別是什麼？
為什麼我們在加密應用中使用 NTT 而不是 FFT？
哪一個是另一個的概括？
TL;DR您需要 NTT 才能在加密應用程序中進行精確算術。
FFT 只是一種用於評估傳統 DFT 的算法，用於復數值（注意實數和整數是複數域的子集，因此它也適用於它們）向量 $ (f_0,\dots,f_{N-1}) $ 長度 $ N $ 這是在復數場上定義的 $ \mathbb{C} $ 使用秩序統一的複根 $ N. $
在這裡，我們有 $$ F(\lambda)=\sum_{k=0}^{N-1} f_k e^{2 \pi i \lambda k/N}= \sum_{k=0}^{N-1} f_k \xi_N^{\lambda k}, \quad \xi_N:=e^{2 \pi i /N}, \lambda=0,1,\ldots,N-1 $$
如此復雜的統一根源存在於所有人 $ N $ ，但是如果 FFT 更有效 $ N $ 是複合的，最高的效率正在獲得 $ N=2^m, $ 對於某個整數 $ m. $
*DFT 的問題：*對於密碼學，我們使用有限對象，實際上可以獲得完全精度，這在復雜領域的實踐中並不適用，因為複單位根的參數是無理的，並且通常不可能進行精確的算術。
現在，NTT，無論是基於有限域還是單位模某些環的整數根，都為我們提供了完整的精度（複雜的 DFT 不能做到這一點，也不能用於加密），並在使用的本機環中進行評估在密碼學中。它們仍然是 DFT。並且對於某些長度可以有有效的實現。
選擇 NTT：
假設輸入向量是一個序列 $ N $ 非負整數。
一般來說，需要選擇一個模數 $ M $ 這樣 $ 1≤N<M $ 並且每個輸入值都在範圍內 $ [0,M). $ 如果我們說實現加密，我們已經知道模數。
選擇一些整數 $ k≥1 $ 並定義 $ N’=kN+1 $ 作為工作模量。我們需要 $ N’≥M, $ 為簡單起見 $ N’ $ 成為質數。狄利克雷定理保證給定 $ N $ 和 $ M, $ 可選 $ k $ 使 $ N’ $ 一個素數。
因為 $ N’ $ 是素數，乘法群 $ \mathbb{Z}_{N’} $ 有大小 $ φ(N’)=N’−1=kN $ 以及發電機 $ g, $ 這也是一個原始的 (N’-1)th 單位根。
讓 $ \omega≡g^k \pmod N’. $ 然後 $ \omega $ 是原始的 $ N $ th 單位根，根據需要獲得長度的 DFT $ N, $ 所以這是 NNT： $$ F(\lambda)=\sum_{k=0}^{N-1} f_k \omega^{\lambda k},\quad \lambda \in \mathbb{Z}_N. $$ 可以應用蒙哥馬利歸約（或效率較低的巴雷特歸約）來加速 NTT 中的模運算。