本文解释了什么是有限域中的单位根（Roots of Unity），以及它们如何与乘法子群（multiplicative subgroups）相互交织。假设读者已经熟悉上一章关于循环群基本定理（Fundamental Theorem of Cyclic Groups）的内容。

该定理指出，给定一个阶为 $q-1$ 的乘法群 $\mathbb{F}_q^*$，当 $k$ 整除 $q-1$ 时，存在一个唯一的阶为 $k$ 的子群。反之，如果 $k$ 不能整除 $q-1$，则不存在阶为 $k$ 的子群。

该定理还指出，如果 $g$ 是 $\mathbb{F}_q^*$ 的生成元，那么 $g^\frac{q-1}{k}$ 将生成阶为 $k$ 的子群。

在本文中，我们将证明该子群的所有元素就是所谓的 $k$ 次单位根（$k$-th roots of unity），而生成元 $\omega$ 则是所谓的 $k$ 次本原单位根（primitive $k$-th root of unity）。

本章的动机与目标

在有限域中计算 $1$ 的平方根很容易：它们是与 $1$ 和 $-1$ 同余的数（分别是 $1$ 和 $q - 1$。请记住，在域 $\mathbb{F}_q$ 中，数字 $-x$ 与 $q-x$ 同余）。换句话说，$\sqrt{1} = \{1, q-1 \}$。这个集合是方程 $a^2 \equiv 1$ 的解集，其中 $a$ 是有限域中的一个元素。

但是，如果我们想计算 $1$ 的立方根，或者更一般地，计算 $1$ 的 $k$ 次根，即 $\sqrt[^k]{1}$ 呢？根据定义，$k$ 次单位根是满足方程 $a^k \equiv 1$ 的元素。但我们该如何找到它们呢？

我们可以逐个尝试所有元素——一种暴力求解的方法——但当域包含许多元素时，这是不可行的。幸运的是，有一种简单的方法可以找到所有的根。在有限域 $\mathbb{F}_q$ 中，$k$ 次单位根恰好是阶为 $k$ 的乘法子群中的元素。 该定义假设 $k$ 整除 $q-1.$

用最坚定的语气来说：如果有限域中的一个元素 $a$ 属于阶为 $k$ 的乘法子群，那么它就是一个 $k$ 次单位根，并且 $a^k\equiv1$。反之，如果一个元素 $a$ 是 $k$ 次单位根（意味着 $a^k\equiv1$），那么它就属于阶为 $k$ 的乘法子群。

术语的等价性

这似乎只是我们在为同一个实体（乘法群中的元素）添加一个新术语，并指出将其进行 $k$ 次方运算等于 1。

在某种意义上，是的，我们正在为同一个实体引入一个新术语：$k$ 次单位根就是阶为 $k$ 的乘法子群中的元素，反之亦然。通常，给同一个实体起两个名字会导致混淆，因此我们需要证明引入“单位根”这一术语是合理的。

当我们在最一般的意义上讨论阶为 $k$ 的循环群时，我们并不能保证选取该群中的一个元素，并将二元运算符应用于该元素自身 $k$ 次就会得到单位元，即 $a^k\equiv1$，或者对于二元运算符 $\star$ 更一般地表示为：

对于一般的循环群，上述性质并不能保证成立，但对于有限域中的单位根，它是必然成立的。

因此，我们可以说单位根具有循环群基本定理所指出的它们应有的一切性质，并且它们还具有 $a^k\equiv1$ 的性质。

所以，读者大可放心，仅仅因为你理解了循环群基本定理，你实际上已经对有限群中的单位根有了相当的了解。由于有限域中的单位根构成一个循环子群，循环群基本定理自然适用于它们。

然而，$a^k\equiv1$ 这一额外保证解锁了高效 ZK（零知识）算法直接利用的更多性质。这些性质使我们能够创建高效的算法，例如数论变换（Number Theoretic Transform）和其他零知识证明（Zero-Knowledge Proof）算法，如 PLONK 和 ZK-STARKs。

我们将在后续章节中研究单位根的这些附加性质。本章的重点是定义和示例，旨在建立这样一个认知：当且仅当有限域中的元素 $a$ 属于阶为 $k$ 的乘法子群时，它才具有 $a^k\equiv1$ 的性质。

计算 k 次单位根等同于寻找阶为 k 的乘法子群

在关于循环群基本定理的文章中，我们学习了如何找到阶为 $k$ 的乘法子群的所有元素。首先，我们从乘法群 $\mathbb{F}_q^*$ 的生成元中获取该子群的生成元。然后，利用这个生成元，我们就可以找到阶为 $k$ 的子群的所有元素。

因此，如果 $k$ 整除 $q-1$，寻找 $\mathbb{F}_q$ 的 $k$ 次单位根与寻找阶为 $k$ 的乘法子群没有区别，而这正是我们已经掌握的方法。

我们在本章的目的是证明这种等价性——即当 $k$ 整除 $q-1$ 时，所有 $k$ 次单位根组成的群与阶为 $k$ 的乘法子群是等价的。

为此，我们需要证明以下两个命题：

1. 阶为 $k$ 的乘法子群中的每个元素 $a$ 都满足 $a^k\equiv 1$。
2. 假设 $k$ 整除 $q-1$。那么，$\mathbb{F}_q^*$ 中每个满足 $a^k\equiv 1$ 的元素 $a$ 都属于唯一一个阶为 $k$ 的子群。

我们将通过例子来探讨这两个命题，以说明它们是成立的。由于正式的证明在数学上可能有些要求，我们将把部分证明推迟到附录中供感兴趣的读者阅读，尽管我们已经努力使证明尽可能通俗易懂。

1. 阶为 $k$ 的子群中的每个元素 $a$ 都满足 $a^k\equiv 1$

第一个命题表明，阶为 $k$ 的乘法子群的所有元素都是 $k$ 次单位根。

然而，这不足以确立所有 $k$ 次单位根组成的群与阶为 $k$ 的乘法子群之间的等价性（当 $k$ 整除 $q-1$ 时），因为它不能保证所有的 $k$ 次单位根都属于该子群——这将在命题 2 中讨论。

我们将以该命题的证明作为本节的开始，然后通过例子展示该命题是成立的。

命题 1 的证明

回想一下关于循环群基本定理的文章，唯一一个阶为 $k$ 的子群是由 $\omega = g^{\frac{q-1}{k}}$ 生成的，其中 $g$ 是乘法群 $\mathbb{F}_{q}^*$ 的生成元。我们将 $\langle\omega\rangle$ 称为通过对 $\omega$ 进行连续的模 $q$ 幂运算而生成的元素集合：

令 $\omega^m$ 为 $\langle\omega\rangle$ 中的任意元素，其中 $0\le m\le k-1$。目标是证明 $(\omega^m)^k\equiv 1$。

下面的证明假设生成元具有 $\omega^k \equiv 1$ 的性质；关于该事实的证明请参见附录 A。

让我们如下计算 $(\omega^m)^k$：

因此，阶为 $k$ 的子群中的每个元素，当进行 $k$ 次方运算时，结果都等于 1。

命题 1 在 $\mathbb{F}_7 = \{0,1,2,3,4,5,6\}$ 中的示例

在这个例子中，我们有 $q-1 = 7-1 = 6$。同时，元素 $g = 3$ 是乘法群 $\mathbb{F}_q^* = \{1,2,3,4,5,6\}$ 的生成元。

本文不讨论如何寻找乘法群的生成元，但 galois 库提供了一种快速的方法。给定域 $\mathbb{F}_q$，寻找生成元的一种方法是使用 primitive_element 属性，如下所示。

Copy
import galois
GF = galois.GF(7) # define the field
GF.primitive_element # GF(3, order=7) 

阶为 3 的子群

因为 3 能整除 $q-1 = 6$，循环群基本定理保证了唯一一个阶为 3 的子群的存在。

这个子群由 $3^{\frac{q-1}{k}} = 3^{\frac{6}{3}} = 3^{2} = 9\equiv 2\pmod{7}$ 生成。因此，

现在，我们要验证 $\langle 2\rangle$ 中的每个元素 $a$ 都满足 $a^3\equiv 1$。下面是验证过程：

因此，元素 $1, 2$ 和 $4$ 满足 $a^3\equiv 1\pmod{7}$。所以该条件成立。

阶为 2 的子群

因为 2 能整除 $q-1 = 6$，循环群基本定理保证了唯一一个阶为 2 的子群的存在。

这个子群由 $3^{\frac{q-1}{k}} = 3^{\frac{6}{2}} = 3^{3} = 27\equiv 6\pmod{7}$ 生成。因此，

现在，我们要验证 $\langle 6\rangle$ 中的每个元素 $a$ 都满足 $a^2\equiv 1$。

因此，元素 $1$ 和 $6$ 满足 $a^2\equiv 1\pmod{7}$。所以该条件成立。

练习。 验证 $\mathbb{F}_7^*$ 中的每个元素 $a$ 都满足 $a^6\equiv 1$。

2. 如果 $k$ 整除 $q-1$，那么 $\mathbb{F}_q^*$ 中满足 $a^k\equiv 1$ 的每个元素 $a$ 都属于唯一的一个阶为 $k$ 的子群

这一命题断言，在 $k$ 整除 $q-1$ 的前提下，所有的 $k$ 次单位根都属于阶为 $k$ 的乘法子群。

在本节中，我们将通过几个例子来说明这一主张。附录 B 中为感兴趣的读者提供了完整的证明。

在继续之前，让我们考虑一下 $k$ 不能整除 $q-1$ 的情况。在这种情况下，循环群基本定理告诉我们不存在阶为 $k$ 的子群，因此也就不存在任何等价关系。

在 $\mathbb{F}_7 = \{0,1,2,3,4,5,6\}$ 中的示例

在这个例子中，我们有 $q-1 = 7-1 = 6$。同时，元素 $g = 3$ 是乘法群 $\mathbb{F}_q^* = \{1,2,3,4,5,6\}$ 的生成元。

阶为 $k=3$ 的子群

因为 3 能整除 $q-1 = 6$，所以存在一个唯一阶为 3 的子群。这个子群由 $3^{\frac{q-1}{k}} = 3^{\frac{6}{3}} = 3^{2} = 9\equiv 2\pmod{7}$ 生成。因此，

我们要验证 $\mathbb{F}_{7}^*$ 中每个满足 $a^3\equiv 1$ 的元素 $a$ 都属于 $\mathbb{F}_{7}^*$ 中这个唯一的阶为 $k = 3$ 的子群。让我们在 $\mathbb{F}_{7}^*$ 中找出所有这样的元素 $a$，如下所示：

元素 $1, 2$ 和 $4$ 满足 $a^3\equiv 1\pmod{7}$。这三个元素正好是 $\mathbb{F}_{7}^*$ 中阶为 $k =3$ 的子群的成员。因此，$\mathbb{F}_{7}^*$ 中满足 $a^3\equiv 1$ 的每个元素 $a$ 都属于唯一的阶为 $k = 3$ 的子群。

练习。 验证 $\mathbb{F}_7^*$ 中满足 $a^2\equiv 1$ 的每个元素 $a$ 都属于唯一阶为 $k = 2$ 的子群。

在 $\mathbb{F}_{17} = \{0,1,2,\dots,16\}$ 中的示例

在这个例子中，我们有 $q-1 = 17-1 = 16$。同时，元素 $g = 3$ 是乘法群 $\mathbb{F}_q^* = \{1,2,\dots,16\}$ 的生成元，这可以通过 galois 库来验证：

Copy
GF = galois.GF(17) # define the field
GF.primitive_element # GF(3, order=17) 

阶为 $k=4$ 的子群

由于 4 能整除 $q-1 = 16$，存在一个唯一阶为 4 的子群。这个子群由 $3^{\frac{q-1}{k}} = 3^{\frac{16}{4}} = 3^{4} = 81\equiv 13\pmod{17}$ 生成。因此，

我们要验证 $\mathbb{F}_{17}^*$ 中每个满足 $a^4\equiv 1$ 的元素 $a$ 都属于 $\mathbb{F}_{17}^*$ 中这个唯一的阶为 $k = 4$ 的子群。让我们在 $\mathbb{F}_{17}^*$ 中找出所有这样的元素 $a$，如下所示：

元素 $1, 4, 13$ 和 $16$ 满足 $a^4\equiv 1\pmod{17}$。这四个元素正好是 $\mathbb{F}_{17}^*$ 中阶为 $k =4$ 的子群的成员。因此，$\mathbb{F}_{17}^*$ 中满足 $a^4\equiv 1$ 的每个元素 $a$ 都属于唯一阶为 $k = 4$ 的子群。

练习。 验证 $\mathbb{F}_{17}^*$ 中满足 $a^8\equiv 1$ 的每个元素 $a$ 都属于唯一阶为 $k = 8$ 的子群。

$k$ 次本原单位根

$k$ 次本原单位根是一种特殊的 $k$ 次单位根：它是一个能生成所有其他 $k$ 次单位根的 $k$ 次单位根。

由于我们感兴趣的 $k$ 次单位根组成的群与阶为 $k$ 的子群相同，因此 $k$ 次本原单位根正好就是该子群的生成元。

注意：在 $k$ 不能整除 $q-1$ 的情况下（考虑有限域 $\mathbb{F}_q$），可能仍然存在 $k$ 次单位根，但在这种情况下，不存在 $k$ 次本原单位根。

因此，寻找 $k$ 次本原单位根非常简单：这等同于寻找阶为 $k$ 的子群的生成元，而循环群基本定理告诉了我们该如何做到这一点。

$k$ 次本原单位根的正式定义是：它是阶数为 $k$ 的 $k$ 次单位根，其中元素 $a$ 的阶数是指使 $a^r \equiv 1$ 成立的最小正整数 $r$（大于零）。

例如，$4$ 是 $\mathbb{F}_7$ 中的 6 次单位根，因为 $4^6\equiv 1\pmod{7}$，但它不是 6 次本原单位根，因为存在一个低于 6 的幂能使它等于 $1$，具体来说就是 3，即 $4^3 \equiv 1\pmod{7}$。

$k$ 次本原单位根的数量

正如阶为 $k$ 的子群可以有不止一个生成元一样，$k$ 次本原单位根也可以有不止一个。$k$ 次本原单位根的数量与阶为 $k$ 的子群的生成元数量相同。

$k$ 次本原单位根（以及生成元）的数量由欧拉函数 $\phi(k)$ 给出。证明该事实超出了本文的范围。对于我们正在考虑的应用——数论变换（Number Theoretic Transform）——我们只需要一个 $k$ 次本原单位根，假设我们知道 $\mathbb{F}_q^*$ 的一个生成元，就可以利用基本定理来找到它。

在本章的剩余部分，我们将通过示例展示如何使用基本定理寻找 $k$ 次本原单位根，进而找出给定 $k$ 的所有 $k$ 次单位根。

$\mathbb{F}_{17}^*$ 中的 4 次单位根示例

乘法群 $\mathbb{F}_{17}^*$ 的一个生成元是元素 $3$，可以通过使用 galois 库找到。

因此，阶为 4 的子群的生成元是 $\omega = 3^{\frac{16}{4}} = 3^4 \equiv 13$。

根据我们的讨论，这个生成元就是一个 4 次本原单位根。让我们使用 $k$ 次本原单位根的定义来检验一下。我们需要证明：

1. 元素 $13$ 是 4 次单位根。这可以通过检验 $13^4 \equiv 1 \pmod{17}$ 看出。
2. 元素 $13$ 的阶数为 4。这意味着 4 是使得 $13^r \equiv 1 \pmod{17}$ 的最小正整数 $r$。我们将在下面进行检验：

因此，元素 $13$ 是 4 次本原单位根，我们可以使用元素 $13$ 来生成由所有 4 次单位根组成的子群，如下所示：

$\mathbb{F}_{17}^*$ 中的 8 次单位根示例

因为 $g =3$ 是乘法群 $\mathbb{F}_{17}^*$ 的生成元，所以阶为 $8$ 的子群的生成元为 $\omega = 3^{\frac{16}{8}} = 3^2 \equiv 9$。

让我们来检验它也是一个 8 次本原单位根。我们需要检验：

1. 元素 $9$ 是 8 次单位根。这可以通过检验 $9^8 \equiv 1 \pmod{17}$ 看出。
2. 元素 $9$ 的阶数为 8。这意味着 8 是使得 $9^r \equiv 1 \pmod{17}$ 的最小正整数 $r$。我们将在下面进行检验：

因此，元素 $9$ 是 8 次本原单位根，我们可以使用元素 $9$ 来生成由所有 8 次单位根组成的子群，如下所示：

练习。 在 $\mathbb{F}_{17}^*$ 中找到一个 2 次本原单位根以及所有 2 次单位根构成的子群。

结论与总结

我们需要一种高效的方法来寻找所有的 $k$ 次单位根，这正是我们在本文中所研究的内容。总结来说，我们得出了以下结论：

• 如果有限域 $\mathbb{F}_q$ 中的元素 $a$ 满足 $a^k \equiv 1$，则该元素是一个 $k$ 次单位根。
• 如果 $k$ 能整除 $q-1$，那么 $\mathbb{F}_q^*$ 中包含所有 $k$ 次单位根的子群就是由循环群基本定理所保证的那个唯一阶为 $k$ 的子群。
• $k$ 次本原单位根能生成包含所有 $k$ 次单位根的子群。如果 $g$ 是乘法群 $\mathbb{F}_q^*$ 的生成元，且 $k$ 整除 $q-1$，那么元素 $\omega = g^{\frac{q-1}{k}}$ 就是一个 $k$ 次本原单位根。

附录 A

阶为 $k$ 的子群的生成元 $\omega$ 满足**：$\omega^k \equiv 1$**

设 $g$ 为乘法群 $\mathbb{F}_q^*$ 的生成元。回顾循环群基本定理，元素 $\omega = g^{\frac{q-1}{k}}$ 生成唯一阶为 $k$ 的子群。我们的目的是证明 $\omega^k \equiv 1$。

证明。 费马小定理（Fermat’s Little Theorem）指出，如果 $q$ 是一个质数，那么对于任意整数 $g$：

例如，如果 $g = 2$ 且 $q=7$，则 $2^7\equiv 2\pmod{7}$。

如果 $g$ 不能被 $q$ 整除，我们可以在上述等式两边同除以 $g$。这表明费马小定理等价于以下命题：

我们现在如下计算 $\omega^k$：

附录 B

如果 $a\in\mathbb{F}_q^*$ 且 $a^k\equiv1$，则 $a$ 属于唯一的阶为 $k$ 的循环子群。

设 $g$ 为 $\mathbb{F}_q^*$ 的生成元。这等同于说 $g$ 是一个 $(q-1)$ 次单位根。

设 $\omega=g^\frac{q-1}{k}$ 为阶为 $k$ 的乘法子群的生成元（$\omega=g^\frac{q-1}{k}$ 直接来源于循环群基本定理）。

如果 $a\in\mathbb{F}_q^*$ 且 $a^k\equiv1$，那么我们必须证明存在一个整数 $s$ 使得 $\omega^s=a$。$\omega^s\equiv a$ 中整数 $s$ 的存在证明了 $a$ 可以由 $\omega$ 生成，因此属于唯一的阶为 $k$ 的子群。

为了找到这样的 $s$，我们将把 $\omega$ 替换为 $g^\frac{q-1}{k}$，把 $a$ 替换为 $g^m$，从而将 $\omega^s=a$ 转化为：

我们能找出一个使该等式成立的 $s$ 吗？如果我们策略性地选择一个 $s$，使得指数 $\frac{q-1}{k}$ 被抵消并剩下 $m$，我们就会得到：

将 $s=\frac{mk}{q-1}$ 代入方程 ${\left(g^\frac{q-1}{k}\right)}^s\stackrel{?}{=}g^m$ 的左边，我们得到

我们可以看到 $q-1$ 和 $k$ 两项被抵消，剩下 $g^m$。

我们可以将最初的定义 $g^\frac{q-1}{k}=\omega$、$\frac{mk}{q-1}=s$ 和 $g^m=a$ 替换回来，可以看到

因此，如果 $a^k\equiv1$，那么确实存在一个 $s$ 使得 $\omega^s=a$。这里的 $s$ 简单来说就是

其中 $m$ 是 $g^m=a$ 的解，$k$ 是子群的阶，$q$ 是有限域的模数。

然而，我们仍必须证明 $s$ 是一个整数，因为通过将 $\omega$ 提升至分数次幂而生成的值，并不符合由 $\omega$ 生成的子群成员的资格。

证明 $s$ 是整数

为了证明 $\frac{mk}{q-1}$ 是整数，我们需要证明用 $mk$ 除以 $q-1$ 没有余数。

当我们执行除法时，我们应该得到商 $n$ 和余数 $r$。我们要证明 $r$ 必然为 0。

余数不能大于除数（例如，$\frac{11}{5}$ 的余数不能为 5 或更大），所以我们还有以下条件：

通过将格式从 被除数 / 除数 = 商 + 余数 转换为 被除数 = 商 ⋅ 除数 + 余数，我们可以分离出 $\frac{mk}{(q-1)}=n+r$ 中的 $mk$。（为了说明这种重写，请考虑 6/4=1 余 2 可以写成 6 = 4⋅1 + 2）。重写后的形式如下：

为了证明 $r=0$，我们将暂时把 $mk=n\cdot(q-1)+r$ 放在一边，先推导 $mk$ 的另一个性质。

事实： $g^{mk}\equiv1$

$g^{mk}\equiv1$ 可以从以下事实中推导出来：

• $a^k\equiv1$
• $a=g^m$

因此，通过代入可得 $(g^m)^k\equiv1$，并且根据幂的乘方规则可得 $g^{mk}\equiv1$。

将 $mk = n\cdot(q-1) + r$ 代入 $g^{mk}\equiv1$

我们现在有足够的工具来证明 $mk = n\cdot(q-1) + r$ 中的余数 $r$ 为零。提醒读者，$g^{q-1}\equiv1$ 因为 $g$ 是一个 $(q-1)$ 次本原单位根。

我们现在将证明，使用以下定义

• $g^{mk}\equiv1$
• $mk = n\cdot(q-1) + r$
• $g^{q-1}\equiv1$

足以证明 $g^{mk}\equiv g^r$：

由于 $g^{mk}\equiv g^r$ 和 $g^{mk}\equiv 1$，我们可以得出

因为 $g$ 是 $(q-1)$ 次本原单位根，所以 $r$ 只有两种解：

• $r=0$
• $r\equiv q-1$

回想一下 $r$ 被定义为以下等式的解

我们知道，任何有效的除法 $\frac{mk}{q-1}$ 都不会产生 $q-1$ 或更高的余数 $r$，具体来说，余数必须在 $0\le r \lt q-1$ 的范围内。对余数的这一范围限制意味着 $r\neq q-1$。

因此，排除了 $r=q-1$ 的可能性，$g^r\equiv1$ 的唯一解就是 $r=0$（即 $g^0\equiv1$）。

因为 $r=0$，所以 $mk$ 除以 $q-1$ 的结果是一个整数。

最后，由于 $s$ 的定义为

$s$ 是一个整数。