我们将以一种不同寻常的方式开始本章——NTT 算法其实非常简单，不到 20 行代码就能实现。然而，奇怪的是，使其生效的核心思想并没有一个正式的数学名称。因此，我们将冒昧地为这个我们认为是该算法背后的核心定理起一个（主观上）朗朗上口的名字：

多值函数的像保持定理

为了解释像保持定理，我们将复习最后一个关于单位根的（非常简单的）概念，然后再介绍该定理。

嵌套平方根的 $k$ 次根

“$k$ 次单位根”的字面定义是单位根 $a$ 满足 $a^k\equiv1$。换句话说：

因此，如果 $\omega$ 是本原 4 次单位根，那么以下结果也就不足为奇了：

现在，如果 $\omega$ 是本原 8 次单位根，我们进行同样的操作。结果将是：

并且 1 的 8 次根会生成所有的 8 次单位根：

这些观察结果仅仅是定义使然。当然，我们并不想直接计算 1 的平方根。更简单的方法是先找到本原 $k$ 次单位根，然后生成 $\sqrt[8]{1}$ 的答案集合。例如：

Copy
import galois
Fq = 17
k = 8
assert (Fq - 1) % k == 0, "no such subgroup"

GF = galois.GF(Fq)

pr = GF.primitive_root_of_unity(k)

roots = []
for i in range(0,k):
    roots.append(pr**i)
print(roots)

我们还可以观察到：

以此类推。正如上面提到的，直接计算 $\sqrt[k]{1}$ 效率并不高。相反，我们来看看下面这个图，其中每个向下的箭头表示对其上方的数字求平方根：

我们可以从 1 开始，通过不断提取平方根来计算 8 次单位根。

对于任意的 $k$，图示如下。

下面是平方根计算的分布推导过程：

1 的平方根是 $\set{1,\omega^{k/2}}$。$\omega^{k/2}$ 与 -1 同余。

回顾上一章，$\omega^m$ 的平方根是 $\omega^{m/2}$ 和 $-\omega^{m/2}$（假设 $m$ 是偶数）。

因此，$\omega^{k/2}$ 的平方根是 $\set{\omega^{k/4},-\omega^{k/4}}$。

还要记住，$\omega^i$ 的加法逆元是 $\omega^{i+k/2}$。

因此，为了在计算 $-\omega^{k/4}$ 时不使用负号，我们计算 $\omega^{k/4+k/2}=\omega^{k/4+2k/4}=\omega^{3k/4}$。所以 $\omega^{k/2}$ 的平方根是 $\set{\omega^{k/4},\omega^{3k/4}}$。

$\omega^{k/4}$ 的平方根是 ${\omega^{k/8},-\omega^{k/8}}$。同样地，为了去掉负号，我们计算 $\omega^{k/8+k/2}=\omega^{5k/8}$。

至于为什么 $\omega^{3k/4}$ 的平方根是 $\set{\omega^{3k/8},\omega^{7k/8}}$，这留作给读者的练习。

树的高度是 $\log_2n$

通过不断提取 1 的平方根来计算 $k$ 次单位根，会生成一棵高度为 $\log_2(n)$ 的“树”。

概念化树的中间状态

集合

在数学上等价于 8 次单位根。该集合也等价于：

这也等价于：

换句话说：

快速插曲 —— 多值函数与像

诚然，我们上面所做的观察只是 $k$ 次根定义的简单延伸。这些观察结果更有趣的含义将在下一节中展示。不过，首先介绍一些数学术语会很有帮助：

函数的像 (Image of a function) —— 如果我们有一组点用于求取函数值，那么求得的结果集合就是像。例如，如果函数是 $f(x)=2x$，并且我们对 $f$ 求值的定义域是 $\set{1,2}$，那么像就是 $\set{2,4}$。函数的值域 (range) 一词是指函数可能输出的值的集合。在我们的语境中，函数的像是指给定一组输入后实际产生的输出集合。

多值函数 (Multivalued function) —— 对定义域中的单个点可能返回多个求值结果的函数。例如，$\sqrt{x}$ 在 0 处求值返回 0，但 $\sqrt{x}$ 在 1 处求值返回 $\set{1, -1}$。

注意：多值函数 $f(x)=\sqrt{x}$ 的像比它的定义域要大。

牢记这些定义，读者应该能够理解以下陈述：

“$f(x)=x+1$ 在定义域 $\set{0,2}$ 上的像是 $\set{1,3}$”

“多值函数 $f(x)=\sqrt{x}$ 在定义域 $\set{1}$ 上的像是 $\set{1,-1}$”

现在我们来看一组更有趣的观察结果。

$f(x)=x$ 在 $\set{1,...,\omega^7}$ 上的求值像，与 $g(x)=\sqrt[8]{x}$ 在 $\set{1}$ 上的求值像相同 (k = 8)

这一主张只是对上述概念的简单重述，因此我们不再赘述。有趣的部分在于我们如何将此推广到其他函数。

这里的微妙之处在于 $g(x)$ 是一个返回八个元素的多值函数。

$f(x)=ax$ 在 4 次单位根上的求值像，与多值函数 $g(x)=a\sqrt[4]{x}$ 在 $\set{1}$ 上的求值像相同 (k = 4)

请记住，$\sqrt[4]{1}=\set{1,\omega,\omega^2,\omega^3}$，因此 $a\sqrt[4]{1}=\set{a,a\omega,a\omega^2,a\omega^3}$。这与逐个在每个单位根上对 $f$ 求值所得到的像是相同的。因为 $f(x)=ax$：

• $f(1)=a$
• $f(\omega)=a\omega$
• $f(\omega^2)=a\omega^2$
• $f(\omega^3)=a\omega^3$

读者练习： 设 $f(x)=ax+c$。$f(x)$ 在 4 次单位根上的像是什么？多值函数 $g(x)=a\sqrt[4]{x}+b$ 在定义域 $\set{1}$ 上的像又是什么？

在接下来的章节中，我们将展示如何处理像 $f(x)=x^2+x^3$ 这样更复杂的情况，但目前，我们先展示如何针对此处给出的简单情况实际计算多值函数。不过在此之前，让我们先为迄今为止关于像等价性的观察给出一个正式的定义。

$f(x)=x$ 在 4 次单位根上的求值像，与多值函数 $g(x)=\sqrt{x}$ 在 2 次单位根 $\set{1,-1}$ 上的求值像相同 (k = 4)

这个例子与上面的非常相似，只不过我们“瞄准”的定义域不是 $\set{1}$，而是 $\set{1,-1}$。

我们可知：

• $g(1)=\sqrt{1}=\set{1,-1}$
• $g(-1)=\sqrt{-1}=\set{\omega,-\omega}$

这与对 $f$ 在 $\set{1,\omega,-1,-\omega}$ 上求值得到的像相同。

综上所述，如果我们将定义域“缩小” $r$ 倍，并将 $f(x)$ 中的每个 $x$ 替换为 $\sqrt[r]{x}$ 以创建一个新的多值函数 $g$，那么 $f$ 和 $g$ 的像是完全相同的。

现在我们将正式定义我们一直在阐述的这个概念：

NTT 的核心定理：多值函数的像保持定理

设 $\omega$ 为本原 $k$ 次单位根，并设 $\langle\omega\rangle=\set{1,\omega,\omega^2,...}$ 为在 $\mathbb{F}_q$ 中定义的 $k$ 次单位根。

设 $k$ 为 2 的幂。

设 $f(x)$ 为 $\mathbb{F}_q$ 上的多项式。设 $r$ 为小于或等于 $k$ 的 2 的幂。

设 $g(x)$ 为一个多值函数，由将 $f(x)$ 中的每个 $x$ 替换为 $\sqrt[r]{x}$ 创建而来。

设定义域 $\langle\omega\rangle^r$ 为 $\set{\omega^r|\omega\in \langle\omega\rangle}$。请注意，如果 $r=k$，那么 $\langle\omega\rangle^r=\set{1}$。

$f$ 在 $\langle\omega\rangle$ 上的像完全等于 $g$ 在 $\langle\omega\rangle^r$ 上的像。

读者理解上述定理至关重要，因为它是 Number Theoretic Transform 所依赖的关键概念！

这里有一些例子来巩固这个概念：

• $f(x)=x$ 在 4 次单位根上的像等于 $g(x)=\sqrt{x}$ 在 2 次单位根上的像（如上一节所示）。
• $f(x) =x$ 在 16 次单位根上的像等于 $g(x)=\sqrt{x}$ 在 8 次单位根上的像。
• $f(x) =x$ 在 k 次单位根上的像等于 $g_1(x)=\sqrt{x}$ 在 k/2 次单位根上的像。
• $g_1(x)=\sqrt{x}$ 在 k/2 次单位根上的像等于 $g_2(x)=\sqrt[4]{x}$ 在 k/4 次单位根上的像。

下一节将展示 $f(x)$ 稍微复杂一点的例子。

$f(x)=ax+b$ 的像保持定理示例

设 $f(x)=ax+b$，定义域为 4 次单位根 $\set{1,\omega,\omega^2,\omega^3}$。

设 $f_1$ 为多值函数 $a\sqrt{x}+b$，定义域为 $\set{1,-1}$，或者等价为 $\set{1,-\omega^2}$。

设 $f_2$ 为多值函数 $a\sqrt[4]{x}+b$，定义域为 $\set{1}$。

$f$、$f_1$ 和 $f_2$ 的像完全相同：$\set{a+b,a\omega+b,a\omega^2+b,a\omega^3+b}$

与 NTT 的联系

请记住，NTT 的目标是在 $\mathcal{O}(n\log n)$ 时间内对 $k$ 次单位根上的 $f(x)$ 进行求值。换句话说，我们要计算 $f$ 在 $k$ 次单位根上的像。

你可能已经猜到接下来的方向了。

计算 $f(x)$ 在 $k$ 次单位根上的像，等价于计算一个新函数 $g(x)$ 的像，该新函数的定义是针对 $f$ 中的每个 $x$，将其替换为 $x\rightarrow\sqrt[k]{x}$，并在 $\set{1}$ 上进行求值。

然而，这留下了一个悬而未决的问题：

将 $\sqrt[k]{x}$ 展开为 $\set{1,...,\omega^{k-1}}$ 并不能直接带来速度上的提升。在算法上，将 $\sqrt[k]{1}$ 展开为 $k$ 次单位根与对 $k$ 个点上的 $f(x)$ 求值是一样的。这种评估 $f(x)$ 的替代方法对我们有什么帮助呢？

在下一章中，我们将展示如何使用平方根展开来计算多值函数，并解释这种方法如何避免冗余计算。