想像一下，對一個算法的理解如此深入，以至於你可以 - 手動執行 - 脫口而出 - 並且不需要記住任何不自然的技巧 《ZK 書籍》再次擴展，這次教導快速傅立葉變換——具體來說是數論變換 (NTT)。 NTT 算法在 O(n log n) 時間內評估 n 點上的多項式。通常，這樣的評估需要 O(n²) 時間。 儘管快速傅立葉變換已經有許多學習資源，但我們發現它們不令人滿意。 例如，一個非常常見的解釋依賴於「將多項式分成偶數和奇數項」，使用「扭曲因子」和「蝴蝶圖」。然而，這些方法看起來像是偶然的隨機發現，描述了算法而不是解釋它。 我們認為上述特徵是附帶的，與更深層次的——而且更容易理解的——基本概念無關。我們甚至避免使用複數的類比。 我們非常小心，確保學習過程中的每一步都有動機，並且每一步都是對前一步的微小擴展。因此，沒有概念上的飛躍或驚喜的發現。 不要讓章節名稱嚇到你；基本原則只是基本代數。 在 13 章結束時，你將能夠手動計算數論變換！ 接下來的連結。