快速數論變換

基本介紹

• 中文名：快速數論變換
• 外文名：Number Theoretic Transform (NTT)
• 基礎：數論
• 屬性：快速數論變換算法
• 優點：利用分治減少運算次數

簡介

一種快速數論變換算法，這種算法是以數論為基礎，對樣本點為的數論變換，按時間抽取的方法，得到一組等價的疊代方程，有效高速簡化了方程中的計算公式·與直接計算相比，大大減少了運算次數。（見快速傅立葉變換）。

在計算機實現多項式乘法中，我們所熟知的快速傅立葉變換(FFT)是基於n次單位根 (omega) 的優秀性質實現的，而由於其計算時會使用正弦函式和餘弦函式，在不斷運算時無法避免地會產生精度誤差。而多項式乘法有些時候會建立在模域中，在對一些特殊的大質數取模時，便可以考慮用原根g來代替，而這些特殊的大質數的原根恰好滿足的某些性質，這使得多項式乘法在模域中也可以快速的分治合併。