引言

本章将继续探讨群论，重点研究子群（subgroups）和生成元（generators）。最后将介绍本原元（primitive element）的概念。我们假设你已经熟悉群的定义。如果需要复习，请查看this article。

为了建立直观理解，我们从加法群（additive groups）开始，它们非常简单明了，有助于阐明子群和生成元等核心概念。

然后我们将转向模 $n$ 整数乘法群。整数本身在乘法下并不构成群——在 $\mathbb{Z}$ 中只有 $1$ 和 $-1$ 有乘法逆元，因此不满足群公理。为了解决这个问题，我们考虑模 $n$ 的乘法，重点研究小于 $n$ 且与 $n$ 互质（coprime）的整数。这些互质的整数在模 $n$ 下确实具有乘法逆元，它们共同构成了一个良定义的群。这种构造在数论中起着核心作用，也是许多密码学系统的基础。

互质（Coprime）： 如果两个数的最大公约数（GCD）为 1，则这两个数互质。

示例 1： 8 和 15 是互质的，因为
8 的因数：1, 2, 4, 8
15 的因数：1, 3, 5, 15
公因数：1
最大公约数是 1。

示例 2： 12 和 18 不互质，因为
12 的因数：1, 2, 3, 4, 6, 12
18 的因数：1, 2, 3, 6, 9, 18
公因数：1, 2, 3, 6
最大公约数是 6。

最后，我们来研究生成元（generators）——即能够通过重复乘法运算生成整个群或子群的元素。了解生成元可以揭示重要的子群结构，特别是当 $n$ 为素数时，并突显它们在密码学应用中的关键作用。

1. 加法群

加法群使用加法（通常是模某个数的加法）作为运算，单位元为 $0$，元素 $a$ 的逆元为 $-a$，这使得它们的结构相对直观。让我们通过例子来看看它们是如何运作的。

1.1 示例：$({\mathbb{Z}}_6,+)$

作为热身，考虑在加法下的 ${\mathbb{Z}}_6=\{0,1,2,3,4,5\}$。从封闭性（closure）开始：

所有结果都在 $\{0,1,2,3,4,5\}$ 内，因此封闭性成立。检查其他性质：

• 结合律（Associativity）： 分组不改变结果：
  • $(2+3)+4=5+4=9\equiv 3(\mathrm{mod}6)$，
  • $2+(3+4)=2+(7\equiv 1)=3$。
• 单位元（Identity）: $0$ 作为单位元，因为 $3+0=3$（参见表格的第一行或第一列）。
• 逆元（Inverses）: 每个元素都有一个配对元素，相加之和等于 $0(\mathrm{mod}6)$：

因此，$({\mathbb{Z}}_6,+)$ 是一个群，其阶（order，即集合中元素的数量）为 $|{\mathbb{Z}}_6|=6$。

练习 1.1：检查 $({\mathbb{Z}}_9,+)$ 是否为一个群。

提示： 尝试像我们对 ${\mathbb{Z}}_6$ 所做的那样构建加法表。

手动执行此操作可能有些繁琐，因此这里有一个 Python 脚本，它可以为任何 ${\mathbb{Z}}_n$ 生成完整的加法表：

Copy

def print_addition_table(mod):
    header = ["+ mod " + str(mod)] + list(range(mod))
    print(" | ".join(str(h).rjust(4) for h in header))
    print("-" * (6 * (mod + 1)))
    for row in range(mod):
        line = [str(row).rjust(4)]
        for col in range(mod):
            value = row + col
            result = value % mod
            if value >= mod:
                line.append(f"{value} ≡ {result}".rjust(6))
            else:
                line.append(str(result).rjust(6))
        print(" | ".join(line))


# Try it with Z_9
print_addition_table(9)

后续： 在分析了 ${\mathbb{Z}}_9$ 之后，尝试生成 ${\mathbb{Z}}_{10}$ 的表格。你能确定 $({\mathbb{Z}}_{10},+)$ 是否也是一个群吗？

因此，$({\mathbb{Z}}_n,+)$ 是一个阶为 $n$ 的群。这类有限群在模算术和密码学中至关重要。接下来，我们将注意力转向群内的特定元素和子集如何揭示更深层次的结构——通过子群和生成元。

2. 子群与生成元

2.1 理解子群

在研究群时，我们经常会遇到一些子集，它们在相同运算下保留了群的结构。这些特殊的子集被称为子群（subgroups），它们就像是父群的微缩版本。不过，并非所有子集都符合条件——让我们通过例子来探讨什么才能构成子群。

示例 2.1.1：$(\mathbb{Z},+)$ 中的子群

考虑所有整数在加法下构成的群 $(\mathbb{Z},+)$，以及两个熟悉的子集：

• 偶数集合：$\{\dots ,-4,-2,0,2,4,\dots \}$
• 奇数集合：$\{\dots ,-3,-1,1,3,5,\dots \}$

让我们检查偶数集合：

• 封闭性：两个偶数之和也是偶数（例如，$-2+4=2$）。
• 单位元：$0$ 是偶数且包含在集合中。
• 逆元：任何偶数的逆元也是偶数（例如，$2$ 的逆元是 $-2$）。
• 结合律：继承自 $\mathbb{Z}$。

偶数集合满足所有群性质——这是一个有效的子群。

接下来检查奇数集合：

• 封闭性：$1+3=4$，它是偶数——不在集合中。因此封闭性不成立。
• 单位元：$0$ 不是奇数，所以缺少单位元。
• 逆元：对于 $1$，$-1$ 是奇数——但由于封闭性和单位元已经不成立，它不是一个子群。

奇数在加法下不满足子群条件——它们只是一个子集，而不是一个子群。

示例 2.1.2：$({\mathbb{Z}}_8,+)$ 中的子群

现在选取 $({\mathbb{Z}}_8,+)=\{0,1,2,3,4,5,6,7\}$ 并测试两个子集：

• 模 8 偶数：$\{0,2,4,6\}$
• 前半部分：$\{0,1,2,3\}$

对于 $\{0,2,4,6\}$：

• 封闭性：$2+4=6$，$4+6=10\equiv 2(\mathrm{mod}8)$（都在集合中）。
• 单位元：存在 $0$。
• 逆元：$2+6=8\equiv 0$，$4+4=8\equiv 0$，$0+0=0$（所有配对均成立）。
• 结合律：继承自 ${\mathbb{Z}}_8$。

这是一个子群！

对于 $\{0,1,2,3\}$：

• 封闭性：$2+3=5$（不在集合中）。
• 单位元：存在 $0$。
• 逆元：对于 $1$，$0,1,2,3$ 中没有元素能使其相加得到 $0$（例如，$1+3=4(\mathrm{mod}8)$）。

它无法构成群，所以只是一个子集，而不是子群。

定义：群 $G$ 的子集 $H$ 如果在同一运算下也是一个群，即满足封闭性、包含单位元、其所有元素都有逆元，并且继承了 $G$ 的结合律，则称 $H$ 为 $G$ 的子群（subgroup）。

练习 2.1.1： 找出 $({\mathbb{Z}}_5,+)$ 的所有子群。

2.2 加法群中的生成元

既然我们已经了解了子群，接下来探讨单个元素是如何生成它们——甚至生成整个群的。我们将回顾 $({\mathbb{Z}}_6,+)=\{0,1,2,3,4,5\}$，即模 6 加法的加法群，并观察当我们不断将一个元素与自身相加时会发生什么，就像在模 6 的数字上“漫步”一样。

示例 2.2.1：$({\mathbb{Z}}_6,+)$ 中的生成元

尝试 1：

• $1$
• $1+1=2$
• $2+1=3$
• $3+1=4$
• $4+1=5$
• $5+1=6\equiv 0(\mathrm{mod}6)$

这得到了 $\{0,1,2,3,4,5\}={\mathbb{Z}}_6$。不断地加上 $1$ 循环遍历了整个群。

尝试 2：

• $2$
• $2+2=4$
• $4+2=6\equiv 0(\mathrm{mod}6)$
• $0+2=2$

这得到了 $\{0,2,4\}$——只有群的一半。

尝试 3：

• $3$
• $3+3=6\equiv 0(\mathrm{mod}6)$
• $0+3=3$

这得到了 $\{0,3\}$，范围更小了！

尝试 5：

• $5$
• $5+5=10\equiv 4(\mathrm{mod}6)$
• $4+5=9\equiv 3(\mathrm{mod}6)$
• $3+5=8\equiv 2(\mathrm{mod}6)$
• $2+5=7\equiv 1(\mathrm{mod}6)$
• $1+5=6\equiv 0(\mathrm{mod}6)$

这得到了 $\{0,1,2,3,4,5\}={\mathbb{Z}}_6$，覆盖了所有元素，就像 $1$ 一样。

练习 2.2.1：在 $({\mathbb{Z}}_9,+)$ 中，哪些元素生成整个 ${\mathbb{Z}}_9$？哪些元素生成真子群？

2.2.2 由元素生成的子群

现在考虑任意带有二元运算（如加法或乘法）的群 $G$，设 $g$ 是 $G$ 中的一个元素。通过重复对 $g$ 应用群运算，我们可以构成由它生成的元素集合。这个集合记为 $⟨g⟩$，被称为由 $g$ 生成的循环子群（cyclic subgroup generated by $g$）。

例如在加法群中：

对于许多元素来说，$⟨g⟩$ 是一个真子群（proper subgroup）。但是当 $⟨g⟩=G$ 时，我们称 $g$ 是 $G$ 的一个生成元（generator），并且称 $G$ 是一个循环群（cyclic group）。
如示例 2.2.1 所示，我们计算了在模 6 加法下 $({\mathbb{Z}}_6,+)=\{0,1,2,3,4,5\}$ 中各个元素生成的子群。每个元素生成的子群如下：

• $⟨0⟩=\{0\}$（真子群）
• $⟨1⟩=\{0,1,2,3,4,5\}={\mathbb{Z}}_6$
• $⟨2⟩=\{0,2,4\}$（真子群）
• $⟨3⟩=\{0,3\}$（真子群）
• $⟨4⟩=\{0,4,2\}$（真子群）
• $⟨5⟩=\{0,1,2,3,4,5\}={\mathbb{Z}}_6$

元素 $1$ 和 $5$ 生成整个群 ${\mathbb{Z}}_6$，使它们成为生成元，而 $0$、$2$、$3$ 和 $4$ 则生成真子群。

示例 2.2.3：$({\mathbb{Z}}_5,+)$ 中的生成元

现在测试在模 5 加法下的 ${\mathbb{Z}}_5=\{0,1,2,3,4\}$：

• $⟨1⟩=\{0,1,2,3,4\}={\mathbb{Z}}_5$
• $⟨2⟩=\{2,4,6\equiv 1(\mathrm{mod}5),8\equiv 3(\mathrm{mod}5)\}=\{\mathrm{1,2,3,4}\}={\mathbb{Z}}_5$
• $⟨3⟩=\{3,6\equiv 1(\mathrm{mod}5),9\equiv 4(\mathrm{mod}5),7\equiv 2(\mathrm{mod}5)\}=\{\mathrm{1,2,3,4}\}={\mathbb{Z}}_5$
• $⟨4⟩=\{4,8\equiv 3(\mathrm{mod}5),12\equiv 2(\mathrm{mod}5),16\equiv 1(\mathrm{mod}5)\}=\{\mathrm{1,2,3,4}\}={\mathbb{Z}}_5$

每个非零元素都是生成元。

这是因为对于所有 $g\ne 0$，$\gcd (g,5)=1$，且 $5$ 是素数。

结论：在 $({\mathbb{Z}}_n,+)$ 中，一个元素 $g$ 生成整个群当且仅当 $\gcd (g,n)=1$。对于素数 $n$，所有非零元素都是生成元。对于合数 $n$，只有部分元素符合条件。

2.3 代码：探索 $({\mathbb{Z}}_n,+)$ 中的加法生成元

Copy
def additive_closure(a, n):
    """Generates {0, a, 2a, 3a, ...} mod n until it repeats."""
    result = []
    current = 0
    while current not in result:
        result.append(current)
        current = (current + a) % n
    return sorted(result)  # Sorted for readability

# Show generated sets in (Z_6 , +)
print("Z_6:")
for a in range(6):
    print(f"Generated by {a}: {additive_closure(a, 6)}")

# Show generated sets in (Z_5, +)
print("\nZ_5:")
for a in range(5):
    print(f"Generated by {a}: {additive_closure(a, 5)}")

输出：

Copy
(Z_6, +):
Generated by 0: [0]
Generated by 1: [0, 1, 2, 3, 4, 5]
Generated by 2: [0, 2, 4]
Generated by 3: [0, 3]
Generated by 4: [0, 2, 4]
Generated by 5: [0, 1, 2, 3, 4, 5]

(Z_5, +):
Generated by 0: [0]
Generated by 1: [0, 1, 2, 3, 4]
Generated by 2: [0, 1, 2, 3, 4]
Generated by 3: [0, 1, 2, 3, 4]
Generated by 4: [0, 1, 2, 3, 4]

在探讨了加法群之后，我们现在转向它们对应的乘法群。

3. 乘法群

乘法群在乘法（通常是模某个数的乘法）下运算，单位元为 $1$，不过寻找逆元可能会更加微妙，尤其是在有限集合中。为了说明这一点，我们将使用模 7 乘法作为一个具体例子来探讨。

3.1 示例：

考虑 ${\mathbb{Z}}_7=\{0,1,2,3,4,5,6\}$：

• 封闭性成立，例如，$2\times 5=10\equiv 3$，在集合中。
• 单位元：单位元是 $1$，但这对于 $0$ 不成立，$0$ 没有逆元；
• 逆元：每个非零元素都有一个逆元：
  • $1\times 1=1$
  • $2\times 4=8\equiv 1(\mathrm{mod}7)$
  • $3\times 5=15\equiv 1(\mathrm{mod}7)$
  • $4\times 2=8\equiv 1(\mathrm{mod}7)$
  • $5\times 3=15\equiv 1(\mathrm{mod}7)$
  • $6\times 6=36\equiv 1(\mathrm{mod}7)$

由于 $0$ 没有逆元，$({\mathbb{Z}}_7,\times )$ 不是一个群。但如果我们去掉 $0$，只考虑非零元素——即 ${\mathbb{Z}}_7\setminus \{0\}=\{1,2,3,4,5,6\}$——我们就确实得到了一个在乘法下的群。这个集合通常记为 ${\mathbb{Z}}_7^{\ast }$，是一个阶为 6 的群。

你可以使用以下代码生成任何模数 $n$ 的乘法表：

Copy
def print_multiplication_table(mod):
    header = ["× mod " + str(mod)] + list(range(mod))
    print(" | ".join(str(h).rjust(4) for h in header))
    print("-" * (6 * (mod + 1)))

    for row in range(mod):
        line = [str(row).rjust(4)]
        for col in range(mod):
            value = row * col
            result = value % mod
            if value >= mod:
                line.append(f"{value} ≡ {result}".rjust(6))
            else:
                line.append(str(result).rjust(6))
        print(" | ".join(line))

print_multiplication_table(5)

3.2 示例：$({\mathbb{Z}}_6\setminus \{0\},\times )$ 不是一个群

现在让我们测试集合 $\{1,2,3,4,5\}$ 在模 6 乘法下的情况。

现在我们遇到了一个更根本的问题：一些乘法运算结果为 0，而 0 并不属于该集合。因此，这个集合与二元运算符不满足封闭性，所以它不是一个群。

3.3 示例：$({\mathbb{Z}}_8\setminus \{0\},\times )$

作为另一个例子，现在我们考虑 ${\mathbb{Z}}_8\setminus \{0\}=\{1,2,3,4,5,6,7\}$ 中的乘法：

只有元素 $\{1,3,5,7\}$——那些与 8 互质的元素——具有模 8 的乘法逆元：

• $1\times 1=1(\mathrm{mod}8)$
• $3\times 3=9\equiv 1(\mathrm{mod}8)$
• $5\times 5=25\equiv 1(\mathrm{mod}8)$
• $7\times 7=49\equiv 1(\mathrm{mod}8)$

剩下的元素 $\{2,4,6\}$ 都与 8 有公因数，因此没有逆元。所以，${\mathbb{Z}}_8\setminus \{0\}$ 在乘法下不是一个群。

3.4. 什么是 ${\mathbb{Z}}_n^{\ast }$？

集合 ${\mathbb{Z}}_n^{\ast }$ 正式定义为：

也就是说，${\mathbb{Z}}_n^{\ast }$ 由 ${\mathbb{Z}}_n$ 中所有具有模 $n$ 乘法逆元的元素组成。

• 当 $n$ 为素数时，每个非零元素都是可逆的，因此：
  

  $${\mathbb{Z}}_n^{\ast }={\mathbb{Z}}_n\setminus \{0\}$$

• 当 $n$ 为合数时，只有与 $n$ 互质的元素是可逆的。例如：

  • ${\mathbb{Z}}_6^{\ast }=\{1,5\}$
  • ${\mathbb{Z}}_8^{\ast }=\{1,3,5,7\}$

在这两种情况下，${\mathbb{Z}}_n^{\ast }$ 都在乘法下构成一个群。然而，完整集合 ${\mathbb{Z}}_n\setminus \{0\}$ 并不总是能构成群——除非 $n$ 是素数。

前面我们用 ${\mathbb{Z}}_n\setminus \{0\}$ 来论证当 $n$ 为合数时，逆元的缺失（以及零因子的存在）会破坏群结构。这种区别不仅仅是技术上的：它在理解模算术、密码学算法和数论中起着核心作用。

在下一节中，我们将探讨当 $n$ 为素数时，${\mathbb{Z}}_n^{\ast }$ 的结构会如何变化。

3.5 为什么素数模数可行

这些失效情况促使我们使用素数模数（prime moduli）。在 $\{\mathrm{1,2},\dots ,p-1\}$（其中 $p$ 为素数）中，每个元素都有逆元。事实上，这由数论中的一个经典结果所保证。

考虑模 $n$ 下 $\{1,2,\dots ,n-1\}$ 的规律：

• 如果 $n$ 不是素数，由于零因子和缺失逆元，它不是一个群（例如，$n=6,8$）。
• 如果 $n$ 是素数，它就是一个群。

3.6 计算逆元的 Python 代码

最简单、最高效的方法之一是使用 Python 内置的
pow(a, -1, p) 来计算模逆元。在底层，这之所以有效是因为一个名为费马小定理（Fermat’s Little Theorem）的著名数论结果，它保证了逆元的存在并告诉我们：

当模数 $p$ 为素数且 $a$ 不被 $p$ 整除时。

以下是一个示例：

Copy
def mod_inverse(a, p):  
    return pow(a, -1, p)

# Test for Z_7^*
def test_inverses(p):
    print(f"Testing inverses modulo {p}:")
    for a in range(1, p):
        inv = mod_inverse(a, p)
        print(f"Inverse of {a} mod {p} is {inv} (check: {a} * {inv} = {a * inv % p})")

if __name__ == "__main__":
    p = 7
    test_inverses(p)

输出：

Copy
Testing inverses modulo 7:
Inverse of 1 mod 7 is 1 (check: 1 * 1 = 1)
Inverse of 2 mod 7 is 4 (check: 2 * 4 = 1)
Inverse of 3 mod 7 is 5 (check: 3 * 5 = 1)
Inverse of 4 mod 7 is 2 (check: 4 * 2 = 1)
Inverse of 5 mod 7 is 3 (check: 5 * 3 = 1)
Inverse of 6 mod 7 is 6 (check: 6 * 6 = 1)

3.7 练习

数学练习：

1. 使用 Python 的 pow(a, -1, n) 函数或计算器，找出下列的模逆元（如果存在的话）。对于素数模数，你可以选择使用费马小定理：

   • $3^{-1}\mathrm{mod}11$
   • $7^{-1}\mathrm{mod}26$
   • $4^{-1}\mathrm{mod}15$

2. 在 ${\mathbb{Z}}_{12}^{\ast }$ 中，$a$ 取哪些值时存在模逆元？

编程练习：

1. 编写一个函数 list_all_inverses(n)，返回一个包含 ${\mathbb{Z}}_n^{\ast }$ 中所有元素及其逆元（如果存在）的字典。

2. 编写一个程序，接收用户输入的 a 和 n，并检查模逆元是否存在。如果存在，打印该逆元。用不同的值进行尝试，看看你会有什么发现。

3. 挑战： 挑选几个较小的素数 p，编写一个程序检查对于 {1, 2, ..., p - 1} 中的所有 a，是否都满足
   pow(a, p - 1, p) == 1。
   这对于每个 a 都成立吗？如果 p 不是素数会发生什么？

4. 乘法群中的生成元

我们现在将注意力转向乘法群中的生成元。为了建立直观理解，我们从 ${\mathbb{Z}}_7^{\ast }=\{1,2,3,4,5,6\}$ 中的具体示例开始，探索单个元素如何通过重复乘法生成整个群——或仅仅是群的一部分。

示例 4.1：$({\mathbb{Z}}_7^{\ast },\times )$

尝试 3：

• $3^1=3$
• $3^2=9\equiv 2(\mathrm{mod}7)$
• $3^3=27\equiv 6(\mathrm{mod}7)$
• $3^4=81\equiv 4(\mathrm{mod}7)$
• $3^5=243\equiv 5(\mathrm{mod}7)$
• $3^6=729\equiv 1(\mathrm{mod}7)$

$⟨3⟩=\{1,2,3,4,5,6\}={\mathbb{Z}}_7^{\ast }$。元素 $3$ 是一个生成元。

尝试 2：

• $2^1=2$
• $2^2=4$
• $2^3=8\equiv 1(\mathrm{mod}7)$

$⟨2⟩=\{1,2,4\}$，是一个子群，而不是整个群。

尝试其他元素：

• $4$：$4,16\equiv 2,8\equiv 1$ $\Rightarrow \{1,2,4\}$
• $5$：$5,25\equiv 4,20\equiv 6,30\equiv 2,10\equiv 3,15\equiv 1$ $\Rightarrow {\mathbb{Z}}_7^{\ast }$
• $6$：$6,36\equiv 1$ $\Rightarrow \{1,6\}$

总结：

4.1 本原元

正如我们所见，在加法群 $({\mathbb{Z}}_p,+)$ 中，当 $p$ 为素数时，保证每个非零元素都是生成元。也就是说，重复地将任何非零元素与自身相加，最终将循环遍历群中的所有元素。然而，在乘法群 $({\mathbb{Z}}_p^{\ast },\times )$ 中，只有部分元素是生成元——这些被称为本原元（primitive elements）。这种对比突出了一种根本的区别：基于素数的加法群始终是循环的，且所有非零元素均为生成元；而基于素数的乘法群也是循环的，但只有部分元素能作为生成元。

定义：如果在 ${\mathbb{Z}}_p^{\ast }$ 中的一个元素 $g$ 满足

$$⟨g⟩=\{g^1,g^2,\dots ,g^{p-1}\}(\mathrm{mod}p)={\mathbb{Z}}_p^{\ast }.$$

则称其为本原元（primitive element）。

以 ${\mathbb{Z}}_7^{\ast }$ 为例：$3$ 和 $5$ 是本原元，而 $2$、$4$ 和 $6$ 不是。

数论中的一个基本结论保证了对于任何素数 $p$，群 ${\mathbb{Z}}_p^{\ast }$ 都是循环群（cyclic），这意味着它始终至少包含一个本原元。这与加法群 $({\mathbb{Z}}_p,+)$ 形成鲜明对比，在加法群中，每个非零元素都能生成整个群。

示例 4.1.1：${\mathbb{Z}}_5^{\ast }=\{1,2,3,4\}$

• 元素 2：
  

  $$\begin{array}{cc}{2}^1& =2(\mathrm{mod}5),\\ 2^2& =4(\mathrm{mod}5),\\ 2^3& =8\equiv 3(\mathrm{mod}5),\\ 2^4& =16\equiv 1(\mathrm{mod}5)\end{array}$$
  
  $⟨2⟩=\{1,2,3,4\}={\mathbb{Z}}_5^{\ast }$，因此 $2$ 是一个本原元。

• 元素 3：
  

  $$\begin{array}{cc}{3}^1& =3(\mathrm{mod}5),\\ 3^2& =9\equiv 4(\mathrm{mod}5),\\ 3^3& =27\equiv 2(\mathrm{mod}5),\\ 3^4& =81\equiv 1(\mathrm{mod}5)\end{array}$$
  
  $⟨3⟩=\{1,2,3,4\}={\mathbb{Z}}_5^{\ast }$，因此 $3$ 也是一个本原元。

示例 4.1.2：${\mathbb{Z}}_{11}^{\ast }=\{1,2,3,4,5,6,7,8,9,10\}$

• 元素 2：
  

  $$\begin{array}{cc}{2}^1& =2(\mathrm{mod}11),\\ 2^2& =4(\mathrm{mod}11),\\ 2^3& =8(\mathrm{mod}11),\\ 2^4& =16\equiv 5(\mathrm{mod}11),\\ 2^5& =10(\mathrm{mod}11),\\ 2^6& =20\equiv 9(\mathrm{mod}11),\\ 2^7& =18\equiv 7(\mathrm{mod}11),\\ 2^8& =14\equiv 3(\mathrm{mod}11),\\ 2^9& =6(\mathrm{mod}11),\\ 2^{10}& =12\equiv 1(\mathrm{mod}11)\end{array}$$
  
  $⟨2⟩=\{1,2,3,4,5,6,7,8,9,10\}={\mathbb{Z}}_{11}^{\ast }$，因此 $2$ 是一个本原元。

• 元素 3：
  

  $$\begin{array}{cc}{3}^1& =3(\mathrm{mod}11),\\ 3^2& =9(\mathrm{mod}11),\\ 3^3& =27\equiv 5(\mathrm{mod}11),\\ 3^4& =15\equiv 4(\mathrm{mod}11),\\ 3^5& =12\equiv 1(\mathrm{mod}11)\end{array}$$
  
  $⟨3⟩=\{1,3,4,5,9\}$，是一个子群，不是整个群。

示例 4.1.3：${\mathbb{Z}}_{17}^{\ast }$

• 元素 3：
  

  $$\begin{array}{cc}{3}^1& =3(\mathrm{mod}17),\\ 3^2& =9(\mathrm{mod}17),\\ 3^3& =27\equiv 10(\mathrm{mod}17),\\ 3^4& =81\equiv 13(\mathrm{mod}17),\\ 3^5& =243\equiv 5(\mathrm{mod}17),\\ 3^6& =729\equiv 15(\mathrm{mod}17),\\ 3^7& =2187\equiv 11(\mathrm{mod}17),\\ 3^8& =6561\equiv 16(\mathrm{mod}17),\\ 3^9& =19683\equiv 14(\mathrm{mod}17),\\ 3^{10}& =59049\equiv 8(\mathrm{mod}17),\\ 3^{11}& =177147\equiv 7(\mathrm{mod}17),\\ 3^{12}& =531441\equiv 4(\mathrm{mod}17),\\ 3^{13}& =1594323\equiv 12(\mathrm{mod}17),\\ 3^{14}& =4782969\equiv 2(\mathrm{mod}17),\\ 3^{15}& =14348907\equiv 6(\mathrm{mod}17),\\ 3^{16}& =43046721\equiv 1(\mathrm{mod}17)\end{array}$$

  $⟨3⟩=\{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16\}={\mathbb{Z}}_{17}^{\ast }$，阶为 $16$（整个群）。因此，$3$ 是 ${\mathbb{Z}}_{17}^{\ast }$ 的一个本原元。

补充说明： 尽管前面提到过 ${\mathbb{Z}}_n^{\ast }$ 始终是一个群，但当 $n$ 不是素数时，它并不总是循环的。相反，当 $n=p$ 为素数时，${\mathbb{Z}}_p^{\ast }$ 始终是循环的。这种区别在实践中（尤其是在密码学中）非常重要，因为我们倾向于使用循环群，所以我们通常选择素数模数以确保 ${\mathbb{Z}}_p^{\ast }$ 具有这种循环结构。

4.2 Python 代码：寻找模素数的本原元

为了找出 ${\mathbb{Z}}_p^{\ast }$ 中的本原元，我们计算由某个候选元素生成的子群，并检查它是否包含了 ${\mathbb{Z}}_p^{\ast }$ 中的所有元素。以下代码通过执行此检查来验证给定元素 $g$ 是否为本原元。你可以使用它来探索并测试更多本原元的例子：

Copy
def is_primitive_element(g, p):
    """Check if g is a primitive element modulo p."""
    required = set(range(1, p))
    generated = set()
    val = 1
    for _ in range(1, p):
        val = (val * g) % p
        generated.add(val)
    return generated == required

def primitive_elements(p):
    """Find all primitive elements of prime p."""
    elements = []
    for g in range(2, p):
        if is_primitive_element(g, p):
            elements.append(g)
    return elements

# Example usage:
prime = 11
print(f"Primitive elements modulo {prime}: {primitive_elements(prime)}")

示例输出：

Copy
Primitive elements modulo 11: [2, 6, 7, 8]

对于更高效的方法，galois 库可以直接计算有限域乘法群中的本原元（对于素数 $p$，这等同于 ${\mathbb{Z}}_p^{\ast }$）。首先，通过 pip install galois 安装该库，然后使用：

Copy
import galois
print(galois.GF(7).primitive_elements)  # Output: [3, 5]

这种方法对大素数进行了优化，非常适合实际应用，而上面手动编写的代码有助于理解本原元的概念。

练习

让我们应用一下刚刚学到的关于生成元和本原元的知识。

1. 使用上面的 Python 代码找出 $({\mathbb{Z}}_{13}^{\ast },\times )$ 的一个生成元。
   （提示：你需要寻找一个能通过它的幂生成 ${\mathbb{Z}}_{13}^{\ast }$ 所有元素的元素。）

2. 使用你的生成元 $g$，以 $g^k$ 的形式列出 ${\mathbb{Z}}_{13}^{\ast }$ 的所有元素。
   （提示：你应该得到 12 个不同的幂。）

3. 对于以下每个 $k\in \{1,2,3,4,6\}$ 的值，写出由 $g^k$ 生成的子群。
   （提示：这种方法有助于你不使用暴力破解就能找到所有的子群。例如，考虑下面的 $k=2$ 情况）

示例：
如果 $g=2$（${\mathbb{Z}}_{13}^{\ast }$ 的一个生成元），那么：

• $g^2=2^2=4$
• 由 $4$ 生成的子群是：
  
  $$⟨4⟩=\{4,4^2=16\equiv 3(\mathrm{mod}13),4^3=64\equiv 12(\mathrm{mod}13),\dots \}=\{4,3,12,9,10,1\}$$

现在尝试对 $k=1,3,4,6$ 执行此操作。
（记住：首先计算 $g^k$，然后列出其在模 13 下的连续幂次，直到循环回到 1。）

4. 利用上面的工作结果列出 $({\mathbb{Z}}_{13}^{\ast },\times )$ 的所有不同子群。
   （提示：$g$ 的某些幂可能会生成相同的子群。）

结论：
本章重点探讨了模素数的乘法群及其子群结构。我们了解到这些群是循环的，这意味着它们可以由单个元素生成——这个元素被称为本原元。我们还探讨了本原元的幂如何生成循环子群，以及不同的幂如何产生不同的子群。

由于我们尚未引入像拉格朗日定理（Lagrange’s Theorem）这样的形式化工具，因此我们以手动方式探索了子群的发现过程——特别是在最后的练习中，我们尝试了几个 $k$ 的值以查看它们会生成哪些子群。在下一章中，你将学习能够系统地确定子群大小和生成元的底层原理。