N17密码学与安全 · 数学基础6 分钟更新于 2026-08-21

从单位根到 NTT

解释有限域单位根如何支撑数论变换，并建立数论知识与多项式快速计算之间的连接。

关键词单位根 · NTT · FFT · 多项式

建议先了解

前面的数论知识最终会进入多项式求值、卷积、密码学和零知识证明。数论变换（Number Theoretic Transform，NTT）可以理解为“在有限域中运行的离散傅里叶变换”。

这一篇先回答三个问题：

完整的正变换、逆变换和蝶形算法会继续拆成单独 Note。

设多项式

f(x)=a_0+a_1x+\cdots+a_{n-1}x^{n-1}.

NTT 选择一组有限域中的点

1,\omega,\omega^2,\dots,\omega^{n-1},

并计算

F_k=f(\omega^k),qquad k=0,1,\dots,n-1.

$\omega$ 必须是原始 $n$ 次单位根，也就是

\omega^n=1

且对 $0<d<n$ ，

\omega^d\neq1.

这样这些求值点才互不重复，并具有可用于分治的周期结构。

当 $n$ 为偶数时，可以把多项式按偶数次幂和奇数次幂拆开：

f(x)=f_{\text{even}}(x^2)+x f_{\text{odd}}(x^2).

在单位根点上求值时， $\omega^{2k}$ 会落入规模减半的单位根集合。于是一个长度为 $n$ 的问题可以递归变成两个长度为 $n/2$ 的问题。

这正是 FFT 和 NTT 获得

O(n\log n)

复杂度的核心结构，而不是简单地“把模运算写进 FFT”。

如果在素域 $\mathbb F_p$ 中进行长度为 $n$ 的 NTT，需要存在原始 $n$ 次单位根。由于

|\mathbb F_p^*|=p-1,

典型条件是

n\mid(p-1).

若 $g$ 是 $\mathbb F_p^*$ 的生成元，可以构造

\omega=g^{(p-1)/n}.

工程中经常选择

n=2^k

并让 $2^k$ 整除 $p-1$ ，这样可以反复二分。

在 $\mathbb F_{17}$ 中，乘法群阶为

17-1=16.

因此可以支持长度为 2、4、8 或 16 的单位根结构。上一篇构造了原始 4 次单位根

\omega=13.

长度 4 的求值点为

1,13,13^2,13^3\pmod{17},

即

1,13,16,4.

这些点互不相同，并满足 $\omega^4=1$ 。

NTT 没有浮点舍入误差，但会受到模数和变换长度的代数条件约束。

整除
  ↓ 定义互质
最大公约数与 Bézout 等式
  ↓ 判断并构造逆元
同余与模逆元
  ↓ 模质数时非零元素都可逆
有限域 F_p
  ↓ 去掉 0 后形成循环乘法群
生成元与元素的阶
  ↓ 构造原始单位根
单位根
  ↓ 提供递归求值点
NTT

每一箭头都表示一个依赖关系。缺少前一层条件，不能直接套用后一层公式。

后续应继续拆分为独立 Note：

参考答案