故事是這樣子的，最近因為工作的關係，頻繁接觸到了錯誤更正碼 (ECC) 中的 Reed-Solomon code 里德-所羅門編碼或是雷德-所羅門編碼（下稱 RS 碼），在學習的過程中，我發現了這篇 Tomverbeure 所寫的 Reed-Solomon Error Correcting Codes from the Bottom Up 十分詳盡，而且切入簡單又好理解，讓我看完立馬看懂相關的程式碼，值得推廣給大家，在徵得作者同意 就透過 AI 整理並翻譯了這篇文。
...故事是這樣子的，最近工作之餘頻繁地遇到 NTT 這個東西，但這個東西不是很好懂，所以想說來筆記一下， 順便用一個簡單的例子來說明 NTT/INTT 的流程與結果。
簡而言之呢，NTT 就是 Nippon Telegraph and Telephone 日本電信電話…欸不是這個 NTT ，這邊要講的是 number-theoretic transform，中文是翻數論轉換。
可以把它看成離散傅立葉轉換 DFT 的一個通用的形式，把一個數或一個多項式分解成多個選定的因子的向量；
反向的 Inverse NTT 則可以反過來從分解開來的向量再轉回去本來的元素。
為什麼要用 NTT 呢？
就像傅立葉轉換把時域的訊號轉到頻域上，讓時域的 convolution 轉成頻域直接相乘；
本來 Finite field 的 convolution ，在 NTT 轉換後可以變直接乘，對整數或多項式的乘法來說很有用。
最近費式數列實在有點紅，讓小弟忍不住也來玩一下。
費式數列給一個初學程式的人都能寫得出來，例如早年我忘了哪位大大在推坑我 python 的時候，就寫了個只要 4 行列出費氏數列的 python 程式，一方面展現 python 在大數運算上的實力，一方面展視了它的簡潔，像是 a , b = a+b, a 這種寫法。
...