想象一下，理解一个算法到如此程度，以至于你可以 - 手动执行 - 记忆中直接执行 - 而且不需要记住任何不自然的技巧 《ZK书》再次扩展，这次教你快速傅里叶变换——特别是数论变换（NTT）。 NTT算法在O(n log n)时间内评估n个点上的多项式。通常，这样的评估需要O(n²)时间。 尽管快速傅里叶变换已经有许多学习资源，但我们发现它们并不令人满意。 例如，一个非常常见的解释依赖于“将多项式分成偶数项和奇数项”，使用“扭曲因子”和“蝴蝶图”。然而，这些方法看起来像是偶然的随机发现，描述了算法而不是解释它。 我们认为上述特征是偶然的，与更深层次的——而且更容易理解的——基本概念无关。我们甚至避免使用复数的类比。 我们非常注意确保学习旅程的每一步都有动机，并且每一步都是对前一步的简单扩展。因此，没有概念上的飞跃或意外发现。 不要让章节名称吓到你；基本原理只是基础代数。 到第13章结束时，你将能够手动计算数论变换！ 链接下一个。