NTT 究竟是什麼?

故事是這樣子的,最近工作之餘頻繁地遇到 NTT 這個東西,但這個東西不是很好懂,所以想說來筆記一下, 順便用一個簡單的例子來說明 NTT/INTT 的流程與結果。

簡而言之呢,NTT 就是 Nippon Telegraph and Telephone 日本電信電話…欸不是這個 NTT ,這邊要講的是 number-theoretic transform,中文是翻數論轉換。
可以把它看成離散傅立葉轉換 DFT 的一個通用的形式,把一個數或一個多項式分解成多個選定的因子的向量; 反向的 Inverse NTT 則可以反過來從分解開來的向量再轉回去本來的元素。
為什麼要用 NTT 呢?
就像傅立葉轉換把時域的訊號轉到頻域上,讓時域的 convolution 轉成頻域直接相乘; 本來 Finite field 的 convolution ,在 NTT 轉換後可以變直接乘,對整數或多項式的乘法來說很有用。

...

 November 19, 2023 |    math  |    python  | 6 min  |  YodaLee

關於費式數列的那些事

最近費式數列實在有點紅,讓小弟忍不住也來玩一下。

費式數列給一個初學程式的人都能寫得出來,例如早年我忘了哪位大大在推坑我 python 的時候,就寫了個只要 4 行列出費氏數列的 python 程式,一方面展現 python 在大數運算上的實力,一方面展視了它的簡潔,像是 a , b = a+b, a 這種寫法。

...

 February 12, 2019 |    math  |    c , python  | 2 min  |  YodaLee