NTT 究竟是什麼？
故事是這樣子的，最近工作之餘頻繁地遇到 NTT 這個東西，但這個東西不是很好懂，所以想說來筆記一下， 順便用一個簡單的例子來說明 NTT/INTT 的流程與結果。
簡而言之呢，NTT 就是 Nippon Telegraph and Telephone 日本電信電話…欸不是這個 NTT ，這邊要講的是 number-theoretic transform，中文是翻數論轉換。
可以把它看成離散傅立葉轉換 DFT 的一個通用的形式，把一個數或一個多項式分解成多個選定的因子的向量；
反向的 Inverse NTT 則可以反過來從分解開來的向量再轉回去本來的元素。
為什麼要用 NTT 呢？
就像傅立葉轉換把時域的訊號轉到頻域上，讓時域的 convolution 轉成頻域直接相乘；
本來 Finite field 的 convolution ，在 NTT 轉換後可以變直接乘，對整數或多項式的乘法來說很有用。