数论变换 (NTT) 是一种在有限域中对多项式在 n 个值上进行求值的算法，其时间复杂度为 O(n log n)。
通常情况下，对多项式求值需要 O(n) 的时间，因此对多项式进行 n 次求值将需要 O(n²) 的时间。
NTT 通过在多项式求值之间复用计算工作来减少运行时间。NTT 算法还能加速多项式的乘法和除法。本教程系列将教授 NTT 算法是如何工作的，以及它为什么能这样工作。本文是对 NTT 教程系列的介绍，并在文末提供了其余教程的目录。
这也是一个快速傅里叶变换教程系列
我们曾苦苦挣扎，不知该称其为“快速傅里叶变换教程系列”还是“数论变换教程系列”。从功能上看，这两种算法是完全相同的——唯一的区别在于我们使用的是有限域还是复数。
有兴趣学习快速傅里叶变换原理的读者也可以跟随本系列，并在学完后对两者都有所了解。
关于本 NTT 教程系列
虽然我们可以简洁地描述 NTT 算法（见下一节），但要理解它的工作原理却出奇地困难。本教程系列：
- 逐步介绍 NTT 所依赖的各种数学技巧
- 引导读者通过第一性原理重新发现 NTT
- 沿途为追求严谨的读者提供可选的数学正确性证明
NTT 算法相当简短，可以通过 AI 一次性生成。请看下面 Gemini 的输出。现在还不用急于理解这些代码；目前只需注意它是多么简短即可。在本系列课程中，我们将逐步解析它的功能。
Prompt: create the NTT algorithm in Python. Show it evaluates the polynomial f(x) = x^2 + 2x + 3 correctly. Use the finite field order 17.
以下是生成的代码（为提高可读性并节省空间进行了极少量的修改）。
def ntt(a, omega, q):
"""
Performs the Number Theoretic Transform (NTT) on list 'a'
over the finite field modulo 'q' using primitive root 'omega'.
"""
N = len(a)
if N == 1:
return a
# Split into even and odd coefficients
a_even = ntt(a[0::2], (omega * omega) % q, q)
a_odd = ntt(a[1::2], (omega * omega) % q, q)
y = [0] * N
w = 1
for i in range(N // 2):
w_a_odd = (w * a_odd[i]) % q
y[i] = (a_even[i] + w_a_odd) % q
y[i + N // 2] = (a_even[i] - w_a_odd) % q
w = (w * omega) % q
return y
def direct_evaluate(x, q):
"""Directly evaluates f(x) = x^2 + 2x + 3 mod q"""
return (x**2 + 2 * x + 3) % q
# --- Configuration ---
q = 17 # Finite field order
omega = 4 # Primitive 4th root of unity mod 17
# f(x) = 3 + 2x + 1x^2 + 0x^3
coefficients = [3, 2, 1, 0]
# 1. Run NTT
ntt_result = ntt(coefficients, omega, q)
# 2. Run Direct Evaluation for Verification
evaluation_points = [(omega**k) % q for k in range(4)]
direct_result = [direct_evaluate(x, q) for x in evaluation_points]
assert (
ntt_result == direct_result
), "Mismatch between NTT and direct evaluation!"
print("\nSuccess! The NTT evaluated the polynomial correctly.")
除空行外，几乎所有的工作都是在这 14 行代码中完成的：
N = len(a)
if N == 1:
return a
# Split into even and odd coefficients
a_even = ntt(a[0::2], (omega * omega) % q, q)
a_odd = ntt(a[1::2], (omega * omega) % q, q)
y = [0] * N
w = 1
for i in range(N // 2):
w_a_odd = (w * a_odd[i]) % q
y[i] = (a_even[i] + w_a_odd) % q
y[i + N // 2] = (a_even[i] - w_a_odd) % q
w = (w * omega) % q
return y
然而，算法的简洁性掩盖了它的复杂性。
大多数 FFT / NTT 教程的误区
粗略浏览上述代码，读者可以看出 NTT 算法的核心在于将多项式系数拆分为偶数和奇数部分，许多关于该主题的教程（以及 AI 的解释）都试图通过奇偶拆分的角度来解释 NTT。
然而，正如我们即将学到的，将系数按奇偶性拆分只是 NTT 所依赖的更深层数学技巧的附带产物。
从根本上说，重新发现 NTT 需要回答“为什么可以在多项式求值之间复用计算？”，而不是“奇偶拆分有什么特别之处？”
例如，考虑如果我们在点 和 处对多项式 进行求值。表面上看， 并没有提供任何关于 应该等于什么的线索。例如， 的平方不能为你提供任何关于 的平方是多少的信息。
多项式求值的速度能快于 并不是显而易见的。
我们在本系列中的目标是，从第一性原理出发，重新发现如何在一个点上对多项式求值能够减少在另一个点上求值所需的工作量。
读者应该按照下面提供的顺序阅读本系列。每一章都会介绍一个易于消化的小子概念，由于后面的章节是建立在前面章节基础上的，因此必须将其内化吸收。
本教程系列的初衷
人们可能会认为，鉴于 NTT 算法对现代工程如此重要，应该会有大量教程不仅描述其机制，还会解释它为什么有效。然而，我们发现现有的解释并不充分，因此我们编写了本教程。在本系列中，你将遇到许多在其他地方找不到的全新视角。我们致力于开发全新的、简化的心智模型，而不是去总结现有的内容。
此外，NTT 算法在结构上反映了 FRI（Fast Reed-Solomon Interactive Oracle Proof of Proximity）。从本质上了解 NTT 算法的工作原理会使 FRI 算法更容易学习。
事实上，FRI 中的“Fast”一词正是因为 FRI 算法与快速傅里叶变换（即 NTT 算法）非常相似。
本教程系列的前置要求
我们期望读者基本熟悉 有限域和模算术。我们将在本系列中定义“子群 (subgroup)”，因此读者应已经熟悉 群 (group) 的概念。阅读 ZK Book 的前六章就足够了。
我们还期望读者具备线性代数的基础知识，例如矩阵的逆。
不需要深入理解抽象代数。我们只需要熟练掌握上面列出的基本词汇即可。
抽象代数的动机驱动学习法
许多读者会发现，我们对有限域中子群和单位根 (roots of unity) 的处理比典型的数学论述更具吸引力，因为我们是在它们“现实世界”应用的上下文中呈现这些概念的。
我们不打算全面论述所涉及的抽象代数主题，只涵盖以下部分：
- 出现在现实世界中的部分（在这里即 NTT 算法）
- 理解现实世界应用所需的前置知识
- 为现实世界的概念提供简化的框架
我们无情地删减了其他所有内容，或者将其标记为供偏好数学的读者选读的内容。我们编写本系列是为软件工程师量身定制的，而不是数学家。
勘误与反馈
如果你在文中发现任何错误或问题，请在 https://github.com/RareSkills/zk-book/tree/prod 提交 issue 或 pull request。
目录
点值表示法的多项式乘法。本章阐述了需要在次二次 (sub-quadratic) 时间内对多项式求值的动机。
乘法子群。子群是理解单位根的前置条件。
循环群基本定理。单位根构成了一个循环子群，该定理说明了它们的性质。
有限域中的单位根。只有当我们在“单位根”上对多项式求值时，NTT 算法才有效，本章将对此进行介绍。对于为了理解快速傅里叶变换而阅读本系列的读者来说，有限域中的单位根与复数中的单位根表现完全一致，即 。
同余为 -1 的单位根。由于单位根构成一个子群，因此每个单位根都有一个（可以被高效计算的）逆元。
在单位圆上可视化单位根。本章展示了如何在单位圆上绘制有限域中的单位根，以及如何轻松地可视化单位根子群中的加法逆元。
范德蒙德矩阵。范德蒙德矩阵将多项式求值表示为多项式系数与求值点的乘积。
单位根的平方。本章是“图像保留定理”章节的前置知识。
单位根的 k/2 次幂。本章（也）是“图像保留定理”章节的前置知识。
单位根的平方根。本章是“图像保留定理”章节的（另一个）前置知识。
图像保留定理。奇怪的是，NTT 所依赖的核心思想并没有一个正式的名称，所以我们发明了“图像保留定理”这个名字。本章介绍的思想是：在一个较小的域上对多项式求值，可以实现在更大域上的计算复用。
平方根多值函数。多值函数返回一组值而不是单一值。这使我们能够“花一次计算的代价获得两次求值”。
手算 NTT。NTT 算法有几种实现变体。我们创建了属于我们自己的实现，它非常适合在纸笔上进行计算，以便学习者能够切身体验该算法。
对 FFT 友好的有限域。本文列出了在实践中用于 NTT 和零知识证明的有限域。
单位根的正交性。本章是“逆数论变换”和“范德蒙德矩阵的逆”的前置知识。
逆数论变换。逆数论变换 (Inverse Number Theoretic Transform) 用于“撤销”数论变换。它接受一组点并以系数形式返回一个多项式。
范德蒙德矩阵的逆。本章证明了范德蒙德矩阵的逆矩阵是另一个范德蒙德矩阵。这一事实使得证明逆数论变换算法的正确性变得轻而易举。
手算逆数论变换。前三章确定了范德蒙德矩阵的逆矩阵也是一个范德蒙德矩阵。因此，我们只需做极小的改动，就可以将数论变换算法复用于逆数论变换。
卷积定理（选读）。卷积定理允许我们优雅地证明基本的多项式乘法等价于执行 NTT、逐点相乘，然后再执行 INTT。
信号流图。NTT 经常使用信号流图进行建模。本章是对该主题的快速回顾。
NTT 中的信号流图。在这里，我们为《手算 NTT》中提出的算法构建了信号流图。生成的图将用于对算法进行推理。
时间抽取 (DIT) 与频率抽取 (DIF)。我们用于手算 NTT 的算法在功能上等同于生产环境下的 NTT 算法实现，但有一些细微的差异。在本章中，我们将展示生产中使用的实际 NTT 实现。
Python 中的基-2 DIT 算法。NTT 有几种算法变体，其中两种是 DIF（频率抽取）和 DIT（时间抽取）。前者在上一章中已做解释；在本章中，我们将解释后者。
Python 中的 NTT、INTT 与快速多项式乘法。在这里，我们用 Python 实现了 NTT 和 INTT，并使用这些算法在 O(n log n) 的时间复杂度内执行多项式乘法。
本文是我们的 ZK Book 中数论变换系列的一部分