模块 5 ：数论变换（NTT）- 快速傅里叶变换

RareSkills 发布于 2026-07-02 08:16 阅读 30

本文是RareSkills零知识证明书中关于数论变换（NTT）的教程系列介绍。NTT是一种在有限域上以O(n log n)时间评估多项式值的算法，与快速傅里叶变换（FFT）在功能上相同。文章指出大多数教程仅关注奇偶分裂，而忽略了算法背后的数学原理，如单位根、循环子群、Vandermonde矩阵等。系列从第一性原理出发，逐步引导读者重新发现NTT，并附有可选证明。前置知识要求：有限域和群论基础。文章还提供代码示例（Python实现NTT）和完整的目录链接。

来自[RareSkills 零知识证明之书](https://learnblockchain.cn/column/117)

### 这也是一个快速傅里叶变换教程系列

我们纠结了很久，到底该把这个系列叫做“快速傅里叶变换教程系列”还是“数论变换教程系列”。从功能上讲，这两个算法是**完全相同**的——唯一的区别在于我们使用的是有限域还是复数。

对学习快速傅里叶变换工作原理感兴趣的读者，也可以跟随本系列理解其中的原理。

### 关于本 NTT 教程系列

虽然可以简洁地**描述** NTT 算法（见下一节），但**理解其工作原理**却出奇地困难。本教程系列：

- 逐步介绍 NTT 依赖的数学技巧集合
- 引导读者从基本原理出发重新发现 NTT
- 沿途提供可选的正确性数学证明，以满足对严谨性感兴趣的读者

NTT 算法相当短小，可以通过一次 AI 提示生成。看看下面 Gemini 的输出。暂时不用理解代码；目前只需注意它有多短。我们将在本系列中逐步构建对代码作用的理解。

```
提示：用 Python 创建 NTT 算法。展示它能正确计算多项式 f(x) = x^2 + 2x + 3。使用模 17 的有限域。
```

以下是生成的代码（为提升可读性和节省空间做了微小修改）。

```python
def ntt(a, omega, q):
    """
    对列表 'a' 执行数论变换 (NTT)
    在模 'q' 的有限域上，使用本原根 'omega'。
    """
    N = len(a)
    if N == 1:
        return a

# 拆分为偶系数和奇系数
    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):
    """直接计算 f(x) = x^2 + 2x + 3 mod q"""
    return (x**2 + 2 * x + 3) % q

## --- 配置 ---
q = 17  # 有限域阶
omega = 4  # 模 17 的四次本原单位根
## f(x) = 3 + 2x + 1x^2 + 0x^3
coefficients = [3, 2, 1, 0]

## 1. 运行 NTT
ntt_result = ntt(coefficients, omega, q)

## 2. 运行直接计算以验证
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
), "NTT 与直接计算结果不匹配！"
print("\n成功！NTT 正确计算了多项式。")
```

几乎所有工作都由这 14 行代码完成（不包括空行）：

```python
    N = len(a)
    if N == 1:
        return a

# 拆分为偶系数和奇系数
    a_even = ntt(a[0::2], (omega * omega) % q, q)
    a_odd = ntt(a[1::2], (omega * omega) % q, q)

return y
```

然而，算法的简短掩盖了其复杂性。

#### 大多数 FFT / NTT 教程的常见错误

浏览上面的代码，读者可以看到 NTT 算法的核心依赖于将多项式系数拆分为偶数部分和奇数部分，许多关于该主题的教程（以及 AI 解释）试图通过奇偶拆分的视角来解释 NTT。

然而，正如我们将要学到的，按系数奇偶性拆分只是 NTT 所依赖的更深层数学技巧的附带结果。

从根本上说，重新发现 NTT 需要回答“为什么可以在多项式求值之间重用计算？”，而不是“奇偶拆分有什么特别之处？”

例如，考虑在点 44 和 77 处求多项式 $f(x)=2x^2+3x+6$ 的值。表面上，$f(4)$ 并不能告诉我们 $f(7)$ 应该等于什么。例如，计算 44 的平方并不能提供关于 77 的平方的任何信息。

多项式求值能比 $O(n^2)$ 快，这一点并非显而易见。

本系列的目标是从基本原理出发，重新发现如何通过在一点求多项式值来减少在另一点求值所需的工作量。

读者应按照下文提供的顺序阅读本系列。每一章都会介绍一个小的、易于理解的子概念，后续章节会在此基础上构建，因此必须内化。

#### 本教程系列的动机

人们可能会认为，鉴于 NTT 算法对现代工程如此基础，应该有大量教程不仅描述其机制，还解释**它为什么有效**。然而，我们发现现有的解释不够充分，因此我们创建了这个教程。你将在本系列中遇到许多你找不到的新视角。我们努力开发新的、简化的心智模型，而不是总结现有内容。

此外，NTT 算法在结构上与 FRI（快速 Reed-Solomon 交互式 Oracle 证明）相似。深入理解 NTT 算法为何有效，将让学习 FRI 算法变得更容易。

事实上，FRI 中的“快速”一词来源于 FRI 算法与快速傅里叶变换（NTT 算法）非常相似。

#### 本教程系列的前置知识

我们期望读者对[有限域和模算术](https://learnblockchain.cn/article/11315)有基本了解。我们将在本系列中定义“子群”，因此读者应已熟悉[群](https://learnblockchain.cn/article/11320)的概念。阅读 [ZK 书籍](https://learnblockchain.cn/column/117)的前六章应该足够了。

我们还期望读者具备线性代数的基础知识，例如矩阵逆。

不需要深入理解抽象代数。我们只需要熟练掌握上述基本词汇。

#### 抽象代数的动机化方法

许多读者会发现我们对有限域中子群和单位根的处理比典型的数学阐述更有趣，因为我们是在“现实世界”出现的上下文中呈现这些概念。

我们并不试图对我们所涵盖的抽象代数主题进行全面处理，只包括那些：

- 在现实世界中出现的部分（即 NTT 算法）
- 理解现实应用所必需的前提知识
- 为现实世界概念提供简化框架的部分

其余部分我们坚决删去或标记为可选阅读，供更偏向数学的读者。我们是为软件工程师，而不是数学家，编写本系列。

### 勘误与反馈

如果你发现文本中的任何错误或问题，请在 [https://github.com/RareSkills/zk-book/tree/prod](https://github.com/RareSkills/zk-book/tree/prod) 提交 issue 或 pull request。

### 模块 5 目录

[点值形式的多项式乘法](https://learnblockchain.cn/article/21780)。本章阐述为什么需要以亚二次时间计算多项式求值。

[乘法子群](https://learnblockchain.cn/article/15679)。子群是理解单位根的前提。

[循环群基本定理](https://learnblockchain.cn/article/21022)。单位根构成一个循环子群，该定理展示了它们的行为。

[有限域中的单位根](https://learnblockchain.cn/article/21545)。NTT 算法仅在多项式在“单位根”上求值时有效，本章介绍单位根。对于那些阅读本系列以理解快速傅里叶变换的读者，有限域中的单位根与复数中的单位根行为相同，即 $e^{i\frac{2\pi k}{n}}$。

[模 -1 的单位根](https://learnblockchain.cn/article/21772)。由于单位根构成子群，每个单位根都有一个逆元（可以高效计算）。

[在单位圆上可视化单位根](https://learnblockchain.cn/article/21773)。本章展示如何在单位圆上绘制有限域中的单位根，以及如何轻松可视化单位根子群中的加法逆元。

[范德蒙德矩阵](https://learnblockchain.cn/article/21771)。范德蒙德矩阵将多项式求值表示为多项式系数与求值点的乘法。

[单位根的平方](https://learnblockchain.cn/article/21774)。本章是像保留定理章节的前提。

[单位根的 k/2 次幂](https://learnblockchain.cn/article/21778)。本章（同样）是像保留定理章节的前提。

[单位根的平方根](https://learnblockchain.cn/article/21775)。本章（又是）像保留定理章节的前提。

[像保留定理](https://learnblockchain.cn/article/21776)。NTT 依赖的关键思想，奇怪的是，它没有正式名称，因此我们发明了“像保留定理”这个名称。本章介绍在较小域上求多项式值可以实现较大域上的计算重用的思想。

[平方根多值函数](https://learnblockchain.cn/article/21777)。多值函数返回一组值而不是单个值。这给了我们“一次计算获得两次求值”的能力。

[手算 NTT](https://learnblockchain.cn/article/21779)。NTT 算法有多种实现变体。我们创建了自己的实现，便于在纸笔上计算，以便学习者能切身感受该算法。

[FFT 友好的有限域](https://learnblockchain.cn/article/21849)。本文列出实际中用于 NTT 和零知识证明的有限域。

[单位根的正交性](https://learnblockchain.cn/article/25153)。本章是逆数论变换和范德蒙德矩阵逆的前提。

[逆数论变换](https://learnblockchain.cn/article/25372)。逆数论变换“撤销”数论变换。它接受一组点值并返回系数形式的多项式。

[范德蒙德矩阵的逆](https://learnblockchain.cn/article/25466)。本章证明范德蒙德矩阵的逆矩阵仍然是范德蒙德矩阵。这一事实使得证明逆数论变换算法的正确性变得简单。

[手算逆数论变换](https://learnblockchain.cn/article/25534)。前三章确立了范德蒙德矩阵的逆也是范德蒙德矩阵。因此，我们可以复用数论变换算法作为逆数论变换，只需做微小改动。

[Rollup定理](https://learnblockchain.cn/article/26431)（可选）。Rollup定理允许我们优雅地证明基本多项式乘法等价于先执行 NTT，再进行点乘，最后执行 INTT。

[信号流图](https://learnblockchain.cn/article/26458)。NTT 经常用信号流图建模。本章是对该主题的快速回顾。

NTT 中的信号流图。这里，我们为《手算 NTT》中呈现的算法构建信号流图。生成的图将用于推理该算法。

时域抽取与频域抽取。我们用于手算 NTT 的算法在功能上等同于生产级 NTT 算法实现，但有一些微小变化。在本章中，我们展示实际生产中使用的 NTT 实现。

Python 中的 Radix-2 DIT 算法。NTT 有几种算法变体，其中两种是 DIF（频域抽取）和 DIT（时域抽取）。前者在前一章中解释；在本章中，我们解释后者。

Python 中的 NTT、INTT 和快速多项式乘法。这里，我们用 Python 实现 NTT 和 INTT，并使用这些算法以 O(n log n) 时间执行多项式乘法。

本文是数论变换系列文章的一部分，出自 [零知识证明之书](https://learnblockchain.cn/column/117)

>- 原文链接： [rareskills.io/post/numbe...](https://rareskills.io/post/number-theoretic-transform)
>- 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～

来自RareSkills 零知识证明之书

这也是一个快速傅里叶变换教程系列

我们纠结了很久，到底该把这个系列叫做“快速傅里叶变换教程系列”还是“数论变换教程系列”。从功能上讲，这两个算法是完全相同的——唯一的区别在于我们使用的是有限域还是复数。

对学习快速傅里叶变换工作原理感兴趣的读者，也可以跟随本系列理解其中的原理。

关于本 NTT 教程系列

虽然可以简洁地描述 NTT 算法（见下一节），但理解其工作原理却出奇地困难。本教程系列：

逐步介绍 NTT 依赖的数学技巧集合
引导读者从基本原理出发重新发现 NTT
沿途提供可选的正确性数学证明，以满足对严谨性感兴趣的读者

提示：用 Python 创建 NTT 算法。展示它能正确计算多项式 f(x) = x^2 + 2x + 3。使用模 17 的有限域。

以下是生成的代码（为提升可读性和节省空间做了微小修改）。

def ntt(a, omega, q):
    """
    对列表 'a' 执行数论变换 (NTT)
    在模 'q' 的有限域上，使用本原根 'omega'。
    """
    N = len(a)
    if N == 1:
        return a

    # 拆分为偶系数和奇系数
    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):
    """直接计算 f(x) = x^2 + 2x + 3 mod q"""
    return (x**2 + 2 * x + 3) % q

## --- 配置 ---
q = 17  # 有限域阶
omega = 4  # 模 17 的四次本原单位根
## f(x) = 3 + 2x + 1x^2 + 0x^3
coefficients = [3, 2, 1, 0]

## 1. 运行 NTT
ntt_result = ntt(coefficients, omega, q)

## 2. 运行直接计算以验证
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
), "NTT 与直接计算结果不匹配！"
print("\n成功！NTT 正确计算了多项式。")

几乎所有工作都由这 14 行代码完成（不包括空行）：

    N = len(a)
    if N == 1:
        return a

    # 拆分为偶系数和奇系数
    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 所依赖的更深层数学技巧的附带结果。

从根本上说，重新发现 NTT 需要回答“为什么可以在多项式求值之间重用计算？”，而不是“奇偶拆分有什么特别之处？”

多项式求值能比 $O(n^2)$ 快，这一点并非显而易见。

本系列的目标是从基本原理出发，重新发现如何通过在一点求多项式值来减少在另一点求值所需的工作量。

读者应按照下文提供的顺序阅读本系列。每一章都会介绍一个小的、易于理解的子概念，后续章节会在此基础上构建，因此必须内化。

本教程系列的动机

人们可能会认为，鉴于 NTT 算法对现代工程如此基础，应该有大量教程不仅描述其机制，还解释它为什么有效。然而，我们发现现有的解释不够充分，因此我们创建了这个教程。你将在本系列中遇到许多你找不到的新视角。我们努力开发新的、简化的心智模型，而不是总结现有内容。

此外，NTT 算法在结构上与 FRI（快速 Reed-Solomon 交互式 Oracle 证明）相似。深入理解 NTT 算法为何有效，将让学习 FRI 算法变得更容易。

事实上，FRI 中的“快速”一词来源于 FRI 算法与快速傅里叶变换（NTT 算法）非常相似。

本教程系列的前置知识

我们期望读者对有限域和模算术有基本了解。我们将在本系列中定义“子群”，因此读者应已熟悉群的概念。阅读 ZK 书籍的前六章应该足够了。

我们还期望读者具备线性代数的基础知识，例如矩阵逆。

不需要深入理解抽象代数。我们只需要熟练掌握上述基本词汇。

抽象代数的动机化方法

许多读者会发现我们对有限域中子群和单位根的处理比典型的数学阐述更有趣，因为我们是在“现实世界”出现的上下文中呈现这些概念。

我们并不试图对我们所涵盖的抽象代数主题进行全面处理，只包括那些：

在现实世界中出现的部分（即 NTT 算法）
理解现实应用所必需的前提知识
为现实世界概念提供简化框架的部分

其余部分我们坚决删去或标记为可选阅读，供更偏向数学的读者。我们是为软件工程师，而不是数学家，编写本系列。

勘误与反馈

如果你发现文本中的任何错误或问题，请在 https://github.com/RareSkills/zk-book/tree/prod 提交 issue 或 pull request。

模块 5 目录

点值形式的多项式乘法。本章阐述为什么需要以亚二次时间计算多项式求值。

乘法子群。子群是理解单位根的前提。

循环群基本定理。单位根构成一个循环子群，该定理展示了它们的行为。

有限域中的单位根。NTT 算法仅在多项式在“单位根”上求值时有效，本章介绍单位根。对于那些阅读本系列以理解快速傅里叶变换的读者，有限域中的单位根与复数中的单位根行为相同，即 $e^{i\frac{2\pi k}{n}}$。

模 -1 的单位根。由于单位根构成子群，每个单位根都有一个逆元（可以高效计算）。

在单位圆上可视化单位根。本章展示如何在单位圆上绘制有限域中的单位根，以及如何轻松可视化单位根子群中的加法逆元。

范德蒙德矩阵。范德蒙德矩阵将多项式求值表示为多项式系数与求值点的乘法。

单位根的平方。本章是像保留定理章节的前提。

单位根的 k/2 次幂。本章（同样）是像保留定理章节的前提。

单位根的平方根。本章（又是）像保留定理章节的前提。

像保留定理。NTT 依赖的关键思想，奇怪的是，它没有正式名称，因此我们发明了“像保留定理”这个名称。本章介绍在较小域上求多项式值可以实现较大域上的计算重用的思想。

平方根多值函数。多值函数返回一组值而不是单个值。这给了我们“一次计算获得两次求值”的能力。

手算 NTT。NTT 算法有多种实现变体。我们创建了自己的实现，便于在纸笔上计算，以便学习者能切身感受该算法。

FFT 友好的有限域。本文列出实际中用于 NTT 和零知识证明的有限域。

单位根的正交性。本章是逆数论变换和范德蒙德矩阵逆的前提。

逆数论变换。逆数论变换“撤销”数论变换。它接受一组点值并返回系数形式的多项式。

范德蒙德矩阵的逆。本章证明范德蒙德矩阵的逆矩阵仍然是范德蒙德矩阵。这一事实使得证明逆数论变换算法的正确性变得简单。

手算逆数论变换。前三章确立了范德蒙德矩阵的逆也是范德蒙德矩阵。因此，我们可以复用数论变换算法作为逆数论变换，只需做微小改动。

Rollup定理（可选）。Rollup定理允许我们优雅地证明基本多项式乘法等价于先执行 NTT，再进行点乘，最后执行 INTT。

信号流图。NTT 经常用信号流图建模。本章是对该主题的快速回顾。

NTT 中的信号流图。这里，我们为《手算 NTT》中呈现的算法构建信号流图。生成的图将用于推理该算法。

Python 中的 Radix-2 DIT 算法。NTT 有几种算法变体，其中两种是 DIF（频域抽取）和 DIT（时域抽取）。前者在前一章中解释；在本章中，我们解释后者。

Python 中的 NTT、INTT 和快速多项式乘法。这里，我们用 Python 实现 NTT 和 INTT，并使用这些算法以 O(n log n) 时间执行多项式乘法。

本文是数论变换系列文章的一部分，出自零知识证明之书

原文链接： rareskills.io/post/numbe...

登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～

0 条评论

模块 5 ：数论变换（NTT）- 快速傅里叶变换

这也是一个快速傅里叶变换教程系列

关于本 NTT 教程系列

大多数 FFT / NTT 教程的常见错误

本教程系列的动机

本教程系列的前置知识

抽象代数的动机化方法

勘误与反馈

模块 5 目录

0 条评论

请输入验证码

登链社区服务条款与隐私政策

登链社区服务条款与隐私政策

登链社区用户服务条款

一、定义

二、服务内容

三、用户权利义务

四、知识产权保护

五、有限保证及服务免责

六、服务变更、中断或终止

七、通知和送达

八、投诉处理

九、法律适用、争议管辖及其他

隐私政策

一、登链社区可能收集的信息内容

二、登链社区收集信息的使用规则

三、登链社区如何共享、转让、公开披露您的个人信息

四、登链社区如何使用 Cookie 和同类技术

五、登链社区如何保护和保存您的个人信息

六、您如何管理个人信息

七、未成年人信息的保护

八、隐私政策的修订和更新

如何联系我们