NTT（Number-theoretic Transform）是一種用於計算多項式乘法的算法，它基於數論中的原根和模運算的性質。NTT算法的核心是將多項式從係數表示法轉換為點值表示法，然後進行點乘，再轉換回係數表示法。這種轉換使得計算過程更加高效，尤其是在處理大數或模運算時。
NTT算法的步驟如下：
確定多項式的次數N，它應該是一個2的整數次冪，並且滿足N≥deg(A(x))+deg(B(x))+1。如果A(x)和B(x)的長度不足N，可以在後面補0。
計算原根ω，即ω=gM−1N(modM)，其中g是原根，M是模數，N是多項式的點數。
對於A(x)和B(x)，分別進行NTT變換，即將它們從係數表示法轉換為點值表示法。
對A(i)和B(i)進行點乘，即對於每個i=0,1,…,N−1，計算C(i)=A(i)⋅B(i)modM。
對C(i)進行逆NTT變換，即將它們從點值表示法轉換回係數表示法。
NTT算法在處理多項式乘法時，可以顯著減少計算次數，尤其是在處理大數或模運算時。此外，NTT算法在取模域上進行操作，使用單位根替換為在取模域的等價數，這使得多項式乘法在模域中也可以快速分治合併。
需要注意的是，NTT算法只能進行以整數為係數的多項式運算，且數組長度和每一項的值都有限制。此外，NTT算法在取模的意義下找到一個新的且為整數的單位根G，用這個根去替代原來的ωn進行運算，因為所有運算就會變成整數運算，所以精度誤差大大降低。