有限循环群的基本定理

有限循环群的基本定理

循环群基本定理提供了关于循环群中循环子群存在的保证。

在有限域上多项式的数论变换（NTT）以及 ZK-STARKs 中的 FRI 运算的上下文中，我们需要阶（元素个数）为 2 的幂的乘法子群。循环群基本定理使我们能够快速确定特定有限域是否具有该阶的乘法子群。

我们将介绍以下预备知识，然后介绍循环群基本定理：

1. 子群的定义
2. 群或子群的阶
3. 乘法群中元素的幂
4. 循环子群、循环群及其生成元

1. 子群的定义

给定一个群 G，G 的一个子集 H 是 G 的一个子群，如果 H 对于 G 中的群运算构成一个群。换句话说，如果我们把自己限制在 H 的元素上，但继续使用 G 的群运算，则群的所有标准仍然成立。最重要的是，运算在 H 中必须是封闭的，因此每当我们对 H 的两个元素应用该运算时，我们必须得到另一个 H 的元素。

子群的例子

在加法下，模 8 的整数集合构成一个群 Z8=({0,1,2,3,4,5,6,7},+)。H1=({0,2,4,6},+) 和 H2=({0,4},+) 都是 Z8 的子群。另一方面，H3=({0,2},+) 不是，因为 (2+2)∉H3

2. 群或子群的阶

群 G 的阶，用 |G| 表示，是它元素的个数。如果一个群不是有限的，则称它的阶是无限的。

群和子群阶的例子

考虑上面例子中的群 Z8。Z8 的阶是 8，表示 |Z8|=8（因为群中正好有 8 个元素）。而且，子群 H=({0,2,4,6},+) 的阶是 4（即 |H|=4）。

3. 乘法群中元素的幂

如果 g∈G，则元素 g 的幂，用 ⟨g⟩ 表示，构成集合 {gk:k∈Z}。例如，考虑模 7 的乘法下的非零整数群，G={1,2,3,4,5,6}。G 中元素 3 的幂如下：

3 的幂 =⟨3⟩={30,31,32,33,34,35,36,…}。

因为：

30=1,31=3,32=9≡2,33=9∗3≡2∗3≡6,34=9∗9≡2∗2≡4,35=9∗9∗3≡2∗2∗3≡12≡5,36=9∗9∗9≡2∗2∗2≡8≡1。

那 37 呢？

37=36∗3≡1∗3≡3(mod7)。

因此，⟨3⟩={1,2,3,4,5,6}。对于每个 k>6 的幂 3k，结果将是已在此列表中的元素之一。

练习：找到由元素 4 生成的集合。

任意元素的幂形成一个子群

设 g 是 G 中的任意元素。元素 g 的幂的集合形成一个子群。换句话说，

⟨g⟩={gk:k∈Z},

是 G 的一个子群。

证明。 见附录

4. 循环子群、循环群及其生成元

设 g 是 G 中的任意元素，则子群 ⟨g⟩={gk:k∈Z} 称为由 g 生成的 G 的循环子群。例如，考虑模 7 的乘法下的非零整数群，G={1,2,3,4,5,6}。由元素 2 生成的循环子群是：

⟨2⟩={20=1,21=2,22=4,23=1,24=2,25=4,26=1}={1,2,4}

练习：找到由元素 6 生成的子群。

循环群的定义

设 g 是 G 中的任意元素。如果 G=⟨g⟩，则我们说 G 是一个循环群，并且 g 是 G 的一个生成元。换句话说，如果一个群包含至少一个生成该群所有元素的元素，则该群是循环的。

循环群和生成元的例子

考虑模 7 的乘法下的非零整数群，G={1,2,3,4,5,6}。由于 ⟨3⟩=G，如上所示，则 G 是一个循环群，并且 3 是 G 的一个生成元。

请注意，⟨2⟩={1,2,4}≠G，这意味着元素 2 不是 G 的生成元，而是 2 生成 G 的一个子群。

练习：确定 5 是否是 G 的生成元

循环群的生成元不一定是唯一的

循环群至少有一个生成元，但生成元不一定是唯一的。换句话说，一个循环群可以有多个生成元，它们中的任何一个都可以生成整个群。循环子群也是如此。

正如你在上面的例子和练习中看到的，元素 3 和 5 都是群 G={1,2,3,4,5,6} 的生成元。

对于另一个例子，考虑模 5 的乘法下的非零整数群。即，{1,2,3,4}。元素 2 和 3 生成整个群。

20=1,30=1,21=2,31=3,22=4,32=4,23=3,33=2。

有限循环群的基本定理

有限循环群基本定理提出了三个主张。设 G 是一个有限循环群，设 H 是 G 的一个子群。

1. H 必然是有限且循环的（意味着 H 有一个生成元）。
2. H 的阶（它拥有的元素个数）是 G 的阶的一个因子。换句话说，H 的阶除以 G 的阶。例如，假设 G 的阶是 6。我们自动知道一个阶为 5 的子群不存在，因为 5 不能整除 6。
3. 如果 q 是 G 的阶，n 除以 q，则大小为 n 的子群必然 存在 并且是 唯一的。 实际上，我们可以立即找到它的生成元：如果 g 是 G 的生成元，则 gqn 是大小为 n 的子群的生成元。这个大小为 n 的子群等于 ⟨gqn⟩。 我们将很快展示这方面的例子。

与拉格朗日定理的联系

循环群基本定理的陈述 (2) 适用于任何有限群 G，即使 G 不是循环的。 这个一般结果被称为 拉格朗日定理。

为简洁起见，我们将此称为循环群基本定理，并理解我们正在处理有限群。

使用循环群基本定理的例子

让我们使用在模 7 乘法下的 G={1,2,3,4,5,6} 作为我们的循环群。我们已经证明 g=3 生成整个群。

阶为 1 的子群

使用循环群基本定理，我们知道 G 有一个阶为 1 的子群，因为 1 除以 6。现在让我们找到此子群的生成元。由于 k=1，我们有 361≡1(mod7)。单位元素 1 显然是大小为 1 的子群的生成元。

阶为 2 的子群

现在让我们找到大小为 2 的子群。我们知道它存在，因为 2 除以 6。在这里，我们有 g=3，n=6 和 k=2。 代入公式，我们得到 gn/k=36/2=33≡6mod7。 元素 6 生成阶为 2 的子群，该子群的元素为 {1,6}。

阶为 3 的子群

由于 3 除以 6，因此存在阶为 3 的子群。而且，元素 3nk=363=32≡2(mod7) 是此子群的生成元，⟨2⟩={20,21,22}={1,2,4}。

阶为 4、5 的子群

没有阶为 4 和 5 的子群，因为这些数字不能整除 6。

阶为 6 的子群

由于 6 除以 6，因此存在阶为 6 的子群。而且，3nk=366=31=3 是此子群的生成元：

⟨3⟩={1,2,3,4,5,6}=G。

练习：考虑在模 11 乘法下具有元素 G={1,2,3,4,5,6,7,8,9,10} 的群。

1. 找到此群的生成元。
2. 该群有一个阶为 5 的子群，因为 5 除以 G 的阶，即 10。找到此子群的生成元并计算其生成的子群。

有限域中阶为 n 的乘法子群

我们可以找到有限域中特定阶的乘法子群。首先，让我们看看有限域的定义：

根据定义，一个域 (F,+,∗) 由两个阿贝尔（二元运算符是可交换的）群组成：

1. 加法群：(F,+)，它是阿贝尔群，在有限域中是有限的。
2. 乘法群：(F∗,∗) （其中 F∗=F∖{0}），它也是阿贝尔群，在有限域中是有限的。

请注意，Fq 表示具有 q 个元素的域，而 Fq∗（Fq 的乘法群）有 q−1 个元素。

在以下定理中，我们看到每个有限域必然包含一个阶为 q–1 的乘法子群（省略 0）。

定理 1：乘法群 Fq∗ 是 q−1 阶的循环群。

如果 Fq 是一个阶为 q 的有限域，则它的乘法群 Fq∗ 是一个阶为 q−1 的循环群。

Fq∗ 形成一个阶为 q−1 的群，这直接来自有限域的定义。

由于证明乘法群的循环性会将我们带到本文范围之外，因此我们将把它作为一个已知事实。

循环群有一个生成元，因此我们知道存在一些 g∈Fq∗ 使得

Fq∗={1,g1,g2,…,gq−2}=⟨g⟩。

有限域中的本原元素（生成元）

在域理论中，有限域 Fq 的一个 本原元素 是该域乘法群的生成元。 定理 1 中的元素 g 是 Fq 中的一个本原元素。

下面的 Python 代码使用 galois 库来识别 F7 中的本原元素（生成元）。

import galois

GF = galois.GF(7)

primitive_elements = GF.primitive_elements
print("本原元素:", primitive_elements)
## 本原元素: [3 5]

## 替代方案，找到一个单独的本原元素
## 当有大量本原元素时适用
primitive_element = GF.primitive_element
print("一个本原元素:", primitive_element)
## 一个本原元素: 3

练习：使用 Python 查找域 F11 的乘法群的所有本原元素。

推论 1：测试阶为 n 的子群——通过有限域中的除数判断存在性

一个有用的推论是，我们可以通过列出 n 的所有除数来快速检查某个大小的子群是否存在。 例如，考虑具有阶为 40 的乘法群 F41∗ 的域 F41。 我们可以快速检查到 F41∗ 具有大小为 8 的子群，因为 8 除以 40。

作为另一个例子，考虑具有阶为 16 的乘法群 F17∗ 的域 F17。 由于 8 除以 16，因此 F17∗ 具有大小为 8 的子群。 类似地，它具有大小为 4 的子群，因为 4 除以 16，并且，你可能已经猜到，F17 也有一个大小为 2 的子群。

为了找到给定大小的乘法子群的生成元，我们可以使用上面基本定理的陈述 (3)。 Fq∗ 的大小是 q−1，因此如果我们有一个本原元素 g 并且想要一个阶为 n 的乘法子群，我们可以为任何本原元素 g 计算 gq−1n。

多合一示例

考虑有限域 F17={0,1,2,…,16}。 对于给定的 n，我们想使用有限循环群基本定理在 F17 中找到阶为 n 的乘法子群。

由于乘法子群 F17∗ 具有阶 q−1=17−1=16，因此我们从循环群基本定理的陈述 (2) 知道，它具有阶为 1、2、4、8 和 16 的子群，最后一个是群本身。

这些子群是循环的，因此每个子群至少有一个生成元。 从定理的陈述 (3) 中，我们知道每个子群的生成元由 gq−1n 给出，其中 g 是完整乘法群的生成元，而 n 是我们想要的子群的大小。

因此，要生成子群，第一步是找到 F17∗ 的生成元，它是 F17 的本原元素。

F17∗ 的生成元

回想一下定理 1，F17∗ 是一个循环群。 为了表明 $mathbb{F}^_{17}∗canbegeneratedbytheelement3,wecancalculateallpowersof3$，我们可以计算 3 的所有幂，如下所示：

30=1,31=3,32=9,33≡9∗3≡10,(27–17=10)34≡10∗3≡13,(30–17=13)35≡13∗3≡5,(39–2∗17=5)36≡5∗3≡15,37≡15∗3≡11,(45–2∗17=11)38≡11∗3≡16,(33–17=16)39≡16∗3≡14,(48–2∗17=14)310≡14∗3≡8,(42–2∗17=8)311≡8∗3≡7,(24–17=7)312≡7∗3≡4,(21–17=4)313≡4∗3≡12,314≡12∗3≡2,(36–2∗17=2)315≡2∗3≡6,316=6∗3≡1,(18–17=1).

317 又是怎么样呢?

317=316∗3≡1∗3=3。

你可以看到，对于所有 i≥17，元素 3i 等于 30,31,32,…,316 之一。 你还可以看到，{1,2,…,16} 中的每个值都出现在 3 的幂列表中。 然后，⟨3⟩={1,2,…,16}=F17∗。

可以在 Python 代码中使用 galois.primitive_elements 找到此生成元。

import galois

GF = galois.GF(17)

primitive_element = GF.primitive_element
print("一个本原元素:", primitive_element)
## 一个本原元素: 3

找到 F17∗ 中阶为 n 的子群

假设我们要确定在有限域 Fq=F17 中是否存在阶为 n=4 的乘法子群。注意，Fq 的乘法群的大小为 q−1。 对于 F17，乘法群 F17∗ 有 q−1=17−1=16 个元素。

回想一下有限循环群基本定理，由于 n 除以 q−1（明确地，4 除以 16），则 gq−1n 是一个生成元，并且 ⟨gq−1n⟩ 是一个大小为 4 的子群。

gq−1n=3164=34≡13(mod17)。

因此，13 是 ∗F17∗∗ 中大小为 4 的子群的生成元，并且

⟨13⟩={130=1,131=13,132≡16,133≡4,134≡1,135≡13,…}。

明确地说，{1,13,16,4} 是子群。

练习： 计算阶数为 2 和 8 的乘法子群。

总结

• 目标是在域 Fq 中找到大小为 n 的乘法子群。
• 如果 G=⟨g⟩={gk:k∈Z}，则 G 是一个循环群，并且 g 是 G 的生成元。
• 如果 Fq 是一个阶数为 q 的有限域，则 (Fq∗,.) 是一个阶数为 q−1 的循环群。
• 循环群基本定理指出，有限域 Fq 具有大小为 n 的子群当且仅当 n 除以 q−1。 此外，该子群的生成元是 gq−1n，其中 g 是乘法群 Fq∗ 的生成元。

附录

我们将检查 ⟨g⟩ 成为 G 的子群所必需的三个条件。

单位元： 由于 1=g0，因此 1∈⟨g⟩。

封闭性： 假设 a,b∈⟨g⟩。 那么我们知道 a=gk 和 b=gm 对于某些 k,m。 应用群运算得到

ab=gkgm=gk+m。

由于 k+m∈Z，因此 ab∈⟨g⟩。

逆元： 假设 a∈⟨g⟩。 那么 a=gk 对于某个 k，

a−1=(gk)−1=g−k。

由于 −k∈Z，所以 a−1∈⟨g⟩。

练习

F31 的乘法子群的所有阶数是什么？每个子群的生成元是什么？

F5 的乘法子群的所有阶数是什么？每个子群的生成元是什么？

F51 的乘法子群的所有阶数是什么？每个子群的生成元是什么？

• 原文链接： rareskills.io/post/funda...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～