乘法子群与本原元素

本文深入探讨了群论中的子群、生成元和本原元素的概念。首先从加法群入手，例如 Z6 和 Z9， 然后转向乘法群，例如 Z7 和 Z11。通过具体的例子和 Python 代码，展示了如何识别子群，找到生成元，并计算模逆。文章还介绍了本原元素的概念，并提供了在 Zp* 中寻找本原元素的 Python 代码。

介绍

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

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

然后，我们将转向 模 n 的整数乘法群（multiplicative groups of integers modulo n）。整数本身在乘法下并不构成群——只有 1 和 -1 在 Z 中有乘法逆元，因此群公理失效。为了解决这个问题，我们考虑模 n 的乘法，重点关注小于 n 且与 n 互质（coprime）的整数。这些元素确实（do）有模 n 的乘法逆元，并且它们一起形成一个定义明确的群。这种构造在数论中起着核心作用，并且是许多密码系统的基础。

最后，我们研究生成元（generators）——可以通过重复乘法产生整个群或子群的元素。理解生成元揭示了重要的子群结构，尤其是在 n 为素数时，并突出了它们在密码学应用中的关键作用。

1. 加法群

加法群使用加法（通常模某个数）作为运算，单位元素为 0，元素 a 的逆元为 −a，这使其结构相对简单。让我们深入研究一些例子，看看它们是如何工作的。

1.1 例子：(Z6,+)

为了热身，考虑加法下的 Z6={0,1,2,3,4,5}。首先是闭包性（closure）：3+4=7，或 5+5=10 将我们带到集合之外。为了解决这个问题，我们使用模 6 加法（addition modulo 6）：3+4=7≡1(mod6) 和 5+5=10≡4(mod6)。现在每个结果都停留在 {0,1,2,3,4,5} 中。以下是加法表：

+mod6 0 1 2 3 4 5
0 0 1 2 3 4 5
1 1 2 3 4 5 6≡0
2 2 3 4 5 6≡0 7≡1
3 3 4 5 6≡0 7≡1 8≡2
4 4 5 6≡0 7≡1 8≡2 9≡3
5 5 6≡0 7≡1 8≡2 9≡3 10≡4

每个结果都在 {0,1,2,3,4,5} 中，因此闭包性成立。检查其他性质：

  • 结合律（Associativity）：分组不改变结果：
    • (2+3)+4=5+4=9≡3(mod6),
    • $2 + (3 + 4) = 2 + (7 \equiv 1) = 3$。
  • 单位元（Identity）：0 作为单位元起作用，因为 3+0=3（参见表格的第一行或第一列）。
  • 逆元（Inverses）：每个元素都有一对加起来等于 0(mod6)的逆元：
元素（Element） 逆元（Inverse） 检查（Check）
0 0 0+0=0
1 5 1+5=6≡0
2 4 2+4=6≡0
3 3 3+3=6≡0
4 2 4+2=6≡0
5 1 5+1=6≡0

因此，(Z6,+) 是一个阶（order）（集合中元素的数量）为 |Z6|=6 的群。

练习 1.1：检查 (Z9,+) 是否是一个群。

提示： 尝试像我们对 Z6 所做的那样构建加法表。

手动执行此操作可能有点乏味，因此这里有一个 Python 脚本，它将为任何 Zn 生成完整的加法表：


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)

后续： 在分析 Z9 之后，尝试生成 Z10 的表。你能确定 (Z10,+) 也是一个群吗？

因此，(Zn,+) 是一个阶为 n 的群。像这样的有限群是模块化算术和密码学的关键。接下来，我们将注意力转向群内某些元素和子集如何通过子群和生成元揭示更深层的结构。

2. 子群和生成元

2.1 理解子群

在研究群时，我们经常会遇到在相同运算下保留群结构的子集。这些特殊的子集，称为 子群（subgroups），表现得像父群的微型版本。但并非每个子集都符合条件——让我们通过例子来探索这一点，看看是什么构成了子群。

例子 2.1.1：(Z,+) 中的子群

考虑 (Z,+)，即加法下的所有整数的群，以及两个熟悉的子集：

  • 偶数整数（even integers）的集合：{…,−4,−2,0,2,4,…}
  • 奇数整数（odd integers）的集合：{…,−3,−1,1,3,5,…}

让我们检查偶数整数：

  • 闭包性：两个偶数的和是偶数（例如，−2+4=2）。
  • 单位元：0 是偶数并且包含在内。
  • 逆元：任何偶数的逆元也是偶数（例如，2 的逆元是 −2）。
  • 结合律：从 Z 继承而来。

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

现在检查奇数整数：

  • 闭包性：1+3=4，是偶数——不是集合的一部分。所以闭包性失败。
  • 单位元：0 不是奇数，所以缺少单位元。
  • 逆元：对于 1，−1 是奇数——但由于闭包性和单位元已经失败，所以它不是一个子群。

加法下的奇数整数不满足子群标准——它们只是一个子集，而不是一个子群。

例子 2.1.2：(Z8,+) 中的子群

现在取 (Z8,+)={0,1,2,3,4,5,6,7} 并测试两个子集：

  • 模 8 的偶数（Evens modulo 8）：{0,2,4,6}
  • 前半部分（First half）：{0,1,2,3}

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

  • 闭包性：2+4=6，4+6=10≡2(mod8)（都在集合中）。
  • 单位元：0 存在。
  • 逆元：2+6=8≡0, 4+4=8≡0, 0+0=0（所有配对都有效）。
  • 结合律：由 Z8 保持。

这是一个子群！

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

  • 闭包性：2+3=5（不在集合中）。
  • 单位元：0 存在。
  • 逆元：对于 1，0,1,2,3 中没有元素给出 0（例如，1+3=4(mod8)）。

这未能成为一个群，所以它只是一个子集，而不是一个子群。

定义： 如果群 G 的子集 H 在相同的运算下是一个群，则 H 是一个 子群（subgroup），这意味着它满足闭包性，包含单位元，所有元素都有逆元，并从 G 继承结合律。

练习 2.1.1： 找到 (Z5,+) 的所有子群。

2.2 加法群中的生成元

既然我们已经看到了子群，让我们探索单个元素如何生成它们——甚至整个群。我们将重新审视 (Z6,+)={0,1,2,3,4,5}，即模 6 加法下的加法群，并检查当我们重复将一个元素加到自身时会发生什么，就像在模 6 的数字周围 “行走（walking）” 一样。

例子 2.2.1：(Z6,+) 中的生成元

尝试 1：

  • 1
  • 1+1=2
  • 2+1=3
  • 3+1=4
  • 4+1=5
  • 5+1=6≡0(mod6)

这给出了 {0,1,2,3,4,5}=Z6。重复加 1 会循环遍历整个群。

尝试 2：

  • 2
  • 2+2=4
  • 4+2=6≡0(mod6)
  • 0+2=2

这给出了 {0,2,4}——仅一半的群。

尝试 3：

  • 3
  • 3+3=6≡0(mod6)
  • 0+3=3

这给出了 {0,3}，甚至更小！

尝试 5：

  • 5
  • 5+5=10≡4(mod6)
  • 4+5=9≡3(mod6)
  • 3+5=8≡2(mod6)
  • 2+5=7≡1(mod6)
  • 1+5=6≡0(mod6)

这给出了 {0,1,2,3,4,5}=Z6，覆盖了所有内容，就像 1 一样。

练习 2.2.1： 在 (Z9,+) 中，哪些元素生成整个 Z9？哪些元素生成真子群？

2.2.2 元素生成的子群

现在考虑任何具有二元运算（如加法或乘法）的群 G，令 g 为 G 的一个元素。通过重复将群运算应用于 g，我们可以形成它生成的元素集合。此集合表示为 ⟨g⟩，称为 g 生成的循环子群（cyclic subgroup generated by g）。

例如，在加法群中：

⟨g⟩={g,g+g,g+g+g,…}={n⋅g∣n∈Z}

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

  • ⟨0⟩={0}（真子群）
  • ⟨1⟩={0,1,2,3,4,5}=Z6
  • ⟨2⟩={0,2,4}（真子群）
  • ⟨3⟩={0,3}（真子群）
  • ⟨4⟩={0,4,2}（真子群）
  • ⟨5⟩={0,1,2,3,4,5}=Z6

元素 1 和 5 生成整个群 Z6，使它们成为生成元，而 0、2、3 和 4 生成真子群。

例子 2.2.3：(Z5,+) 中的生成元

现在测试模 5 加法下的 Z5={0,1,2,3,4}：

  • ⟨1⟩={0,1,2,3,4}=Z5
  • ⟨2⟩={2,4,6≡1(mod5),8≡3(mod5)}={1,2,3,4}=Z5
  • ⟨3⟩={3,6≡1(mod5),9≡4(mod5),7≡2(mod5)}={1,2,3,4}=Z5
  • ⟨4⟩={4,8≡3(mod5),12≡2(mod5),16≡1(mod5)}={1,2,3,4}=Z5

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

发生这种情况是因为对于所有 g≠0，gcd(g,5)=1，并且 5 是素数。

结论： 在 (Zn,+) 中，当且仅当 gcd(g,n)=1 时，元素 g 生成整个群。对于素数 n，所有非零元素都是生成元。对于合数 n，只有某些元素符合条件。

2.3 代码：探索 (Zn,+) 中的加法生成元

def additive_closure(a, n):
    """Generates {0, a, 2a, 3a, ...} mod n until it repeats.""" # 生成 {0, a, 2a, 3a, ...} 模 n 直到它重复。
    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("
Z_5:")
for a in range(5):
    print(f"Generated by {a}: {additive_closure(a, 5)}")

输出：

(Z_6, +):
Generated by 0: [0] # 由 0 生成：[0]
Generated by 1: [0, 1, 2, 3, 4, 5] # 由 1 生成：[0, 1, 2, 3, 4, 5]
Generated by 2: [0, 2, 4] # 由 2 生成：[0, 2, 4]
Generated by 3: [0, 3] # 由 3 生成：[0, 3]
Generated by 4: [0, 2, 4] # 由 4 生成：[0, 2, 4]
Generated by 5: [0, 1, 2, 3, 4, 5] # 由 5 生成：[0, 1, 2, 3, 4, 5]

(Z_5, +):
Generated by 0: [0] # 由 0 生成：[0]
Generated by 1: [0, 1, 2, 3, 4] # 由 1 生成：[0, 1, 2, 3, 4]
Generated by 2: [0, 1, 2, 3, 4] # 由 2 生成：[0, 1, 2, 3, 4]
Generated by 3: [0, 1, 2, 3, 4] # 由 3 生成：[0, 1, 2, 3, 4]
Generated by 4: [0, 1, 2, 3, 4] # 由 4 生成：[0, 1, 2, 3, 4]

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

3. 乘法群

乘法群在乘法下运算（通常模某个数），单位元为 1，但找到逆元可能更微妙，尤其是在有限设置中。为了说明这一点，我们将使用模 7 乘法来检查一个具体的例子。

3.1 例子：

考虑 Z7={0,1,2,3,4,5,6}：

×mod7 0 1 2 3 4 5 6
0 0 0 0 0 0 0 0
1 0 1 2 3 4 5 6
2 0 2 4 6 8≡1 10≡3 12≡5
3 0 3 6 9≡2 12≡5 15≡1 18≡4
4 0 4 8≡1 12≡5 16≡2 20≡6 24≡3
5 0 5 10≡3 15≡1 20≡6 25≡4 30≡2
6 0 6 12≡5 18≡4 24≡3 30≡2 36≡1
  • 闭包性 成立，例如，2×5=10≡3，在集合中。
  • 单位元：单位元是 1，但这对于没有逆元的 0 失败；
  • 逆元：每个非零元素都有一个逆元：
    • 1×1=1
    • 2×4=8≡1(mod7)
    • 3×5=15≡1(mod7)
    • 4×2=8≡1(mod7)
    • 5×3=15≡1(mod7)
    • 6×6=36≡1(mod7)

由于 0 没有逆元，因此 (Z7,×) 不是 一个群。但是，如果我们删除 0 并仅考虑非零元素——即 Z7∖{0}={1,2,3,4,5,6} ——我们确实得到了一个乘法下的群。此集合通常表示为 Z7∗，并且是一个阶为 6 的群。

你可以使用此代码为任何模数 n 生成乘法表：

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 例子：(Z6∖{0},×), 不是一个群

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

×mod6 1 2 3 4 5
1 1 2 3 4 5
2 2 4 6≡0 8≡2 10≡4
3 3 6≡0 9≡3 12≡0 15≡3
4 4 8≡2 12≡0 16≡4 20≡2
5 5 10≡4 15≡3 20≡2 25≡1
  • 闭包性：成立。
  • 单位元：1 仍然有效。
  • 逆元：逆元失败。只有 1 和 5 是可逆的：
    • 1×1=1
    • 5×5=25≡1mod6

元素 2、3 和 4 没有产生 1 的对应元素。这种失败的原因是 6 不是素数：它分解为 6=2×3。该因式分解引入了零因子——非零元素，当与其他非零元素相乘时，产生模 n 的零。例如，4×3=12≡0(mod6)，即使 3 和 4 在 Z6 中都是非零的。由于 2、3 和 4 与 6 共享公因子（分别是 2、3 和 2），因此它们无法具有乘法逆元。

3.3 例子：(Z8∖{0},×)

作为另一个例子，让我们现在考虑 Z8∖{0}={1,2,3,4,5,6,7} 中的乘法： | × | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |———-|—–|—–|—–|—–|—–|—–|—–| | 1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | | 2 | 2 | 4 | 6 | 8≡0 | 10≡2 | 12≡4 | 14≡6 | | 3 | 3 | 6 | 9≡1 | 12≡4 | 15≡7 | 18≡2 | 21≡5 | | 4 | 4 | 8≡0 | 12≡4 | 16≡0 | 20≡4 | 24≡0 | 28≡4 | | 5 | 5 | 10≡2 | 15≡7 | 20≡4 | 25≡1 | 30≡6 | 35≡3 | | 6 | 6 | 12≡4 | 18≡2 | 24≡0 | 30≡6 | 36≡4 | 42≡2 | | 7 | 7 | 14≡6 | 21≡5 | 28≡4 | 35≡3 | 42≡2 | 49≡1 |

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

  • 1×1=1(mod8)
  • 3×3=9≡1(mod8)
  • 5×5=25≡1(mod8)
  • 7×7=49≡1(mod8)

其余元素 {2,4,6} 都与 8 共享一个公因子，因此没有逆元。因此，Z8∖{0} 不是 乘法下的群。

3.4 什么是 Zn∗？

集合 *_$\mathbb{Z}n^ $** 正式定义为：

Zn∗={a∈Zn∣gcd(a,n)=1}

也就是说，Zn∗ 由 Zn 中所有具有 模 n 乘法逆元（multiplicative inverse modulo n）的元素组成。

  • 当 n 是素数（n is prime ）时，每个非零元素都是可逆的，因此： Zn∗=Zn∖{0}

  • 当 n 是合数（n is composite）时，只有与 n 互质（coprime）的元素才是可逆的。例如：

    • Z6∗={1,5}
    • Z8∗={1,3,5,7}

在这两种情况下，Zn∗ 在乘法下形成一个 群（group）。但是，完整的集合 Zn∖{0} 并不（does not） 总是形成一个群——除非 n 是素数。

早些时候，我们使用 Zn∖{0} 来说明为什么当 n 是合数时，逆元的缺失（和零因子的存在）会破坏群结构。这种区别不仅仅是技术上的：它在理解模算术、密码学算法和数论中起着核心作用。

在下一节中，我们将探讨当 n 是素数时，Zn∗ 的结构如何变化。

3.5 为什么素数模有效

这些失败激发了 素数模（prime moduli）。在 {1,2,…,p−1} 中，其中 p 是素数，每个元素都有一个逆元。事实上，这由数论中的一个经典结果保证。

考虑 {1,2,…,n−1} 模 n 的模式：

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

3.6 用于计算逆元的 Python 代码

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

当模数 p 是素数并且 a 不能被 p 整除时。

这是一个例子：

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

## Test for Z_7^*
def test_inverses(p):
    print(f"Testing inverses modulo {p}:") # 测试模 {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})") # {a} mod {p} 的逆元是 {inv} (检查: {a} * {inv} = {a * inv % p})

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

输出：

Testing inverses modulo 7: # 测试模 7 的逆元：
Inverse of 1 mod 7 is 1 (check: 1 * 1 = 1) # 1 mod 7 的逆元是 1 (检查: 1 * 1 = 1)
Inverse of 2 mod 7 is 4 (check: 2 * 4 = 1) # 2 mod 7 的逆元是 4 (检查: 2 * 4 = 1)
Inverse of 3 mod 7 is 5 (check: 3 * 5 = 1) # 3 mod 7 的逆元是 5 (检查: 3 * 5 = 1)
Inverse of 4 mod 7 is 2 (check: 4 * 2 = 1) # 4 mod 7 的逆元是 2 (检查: 4 * 2 = 1)
Inverse of 5 mod 7 is 3 (check: 5 * 3 = 1) # 5 mod 7 的逆元是 3 (检查: 5 * 3 = 1)
Inverse of 6 mod 7 is 6 (check: 6 * 6 = 1) # 6 mod 7 的逆元是 6 (检查: 6 * 6 = 1)

3.7 练习

数学练习：

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

    • 3−1mod11
    • 7−1mod26
    • 4−1mod15
  2. 对于 Z12∗ 中的哪些 a 值，模逆元存在？
编码练习：

  1. 编写一个函数 list_all_inverses(n)，该函数返回 Zn∗ 中所有元素的字典，其中包含它们的逆元（如果存在）。

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

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

4. 乘法群中的生成元

我们现在将注意力转向乘法群中的生成元。为了建立直觉，我们从 Z7∗={1,2,3,4,5,6} 中的具体例子开始，探索单个元素如何通过重复乘法生成完整群——或仅生成群的一部分。

例子 4.1：(Z7∗,×)

尝试 3：

  • 31=3
  • 32=9≡2(mod7)
  • 33=27≡6(mod7)
  • 34=81≡4(mod7)
  • 35=243≡5(mod7)
  • 36=729≡1(mod7)

⟨3⟩={1,2,3,4,5,6}=Z7∗。元素 3 是一个生成元。

尝试 2：

  • 21=2
  • 22=4
  • 23=8≡1(mod7)

⟨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^*$
  • 6: $6, 36 \equiv 1\Rightarrow \{1, 6\}$

总结：

元素（Element） 生成集合（Generated Set） 大小（Size） 生成元？（Generator?）
2 {1,2,4} 3 ❌
3 {1,2,3,4,5,6} 6 ✅
4 {1,2,4} 3 ❌
5 {1,2,3,4,5,6} 6 ✅
6 {1,6} 2 ❌

4.1 本原元素

正如我们所看到的，在加法群 (Zp,+) 中，其中 p 是素数，保证每个非零元素都是一个生成元。也就是说，重复添加任何非零元素最终将循环遍历群的所有元素。但是，在乘法群 (Zp∗,×) 中，只有某些元素是生成元 —— 这些被称为 本原元素（primitive elements）。这种对比突出了一个根本区别：素数上的加法群总是循环的，所有非零元素都是生成元，而素数上的乘法群是循环的，但只有一部分元素可以用作生成元。

定义： 如果 ⟨g⟩={g1,g2,…,gp−1}(modp)=Zp∗，则元素 g∈Zp∗ 是一个 本原元素（primitive element）。

例如，对于 Z7∗：3 和 5 是本原元素，而 2、4 和 6 不是。

数论中的一个基础结果保证对于任何素数 p，群 Zp∗ 是 循环的（cyclic），这意味着它总是包含至少一个本原元素。这与加法群 (Zp,+) 形成对比，在加法群 (Zp,+) 中，每个非零元素生成完整群。

例子 4.1.1：Z5∗={1,2,3,4}

  • 元素 2： 21=2(mod5),22=4(mod5),23=8≡3(mod5),24=16≡1(mod5) ⟨2⟩={1,2,3,4}=Z5∗，因此 2 是一个本原元素。

  • 元素 3： 31=3(mod5),32=9≡4(mod5),33=27≡2(mod5),34=81≡1(mod5) ⟨3⟩={1,2,3,4}=Z5∗，因此 3 也是一个本原元素。

例子 4.1.2：Z11∗={1,2,3,4,5,6,7,8,9,10}
  • 元素 2： 21=2(mod11),22=4(mod11),23=8(mod11),24=16≡5(mod11),25=10(mod11),26=20≡9(mod11),27=18≡7(mod11),28=1```python def is_primitiveelement(g, p): """检查 g 是否为模 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): """查找素数 p 的所有原根。""" elements = [] for g in range(2, p): if is_primitive_element(g, p): elements.append(g) return elements

示例用法：

prime = 11 print(f"模 {prime} 的原根：{primitive_elements(prime)}")


**示例输出：**

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

为了获得更有效的方法，galois 库可以直接计算有限域乘法群中的原根，对于素数 p，它对应于 Zp∗。 首先，使用 pip install galois 安装该库，然后使用：

import galois
print(galois.GF(7).primitive_elements)  # 输出：[3, 5]

此方法针对大素数进行了优化，使其非常适合实际应用，而上面的手动代码有助于理解原根的概念。

练习题

让我们应用所学的关于生成器和原根的知识。

  1. 使用上面的 Python 代码找到 $(\mathbb{Z}{13}^, \times)$ 的一个生成器。 (提示： 你正在寻找一个其幂可以生成 $\mathbb{Z}{13}^$ 的所有元素的元素。)

  2. 使用你的生成器 g 列出 $\mathbb{Z}_{13}^_i ntheformg^k$ 的所有元素。(提示： 你应该得到 12 个不同的幂。)

  3. 对于 k∈{1,2,3,4,6} 的以下每个值，写出由 gk 生成的子群。 (提示： 这种方法可以帮助你找到所有子群，而无需暴力破解。 例如，考虑下面的 k=2 的情况)

示例： 如果 g=2 (Z13∗ 的生成器)，则：

  • g2=22=4
  • 由 4 生成的子群是： ⟨4⟩={4,42=16≡3(mod13),43=64≡12(mod13),…}={4,3,12,9,10,1}

现在尝试 k=1,3,4,6。 (记住： 首先计算 gk，然后列出其连续的模 13 的幂，直到你循环回到 1。)

  1. 使用你上面的工作来列出 $(\mathbb{Z}{13}^, \times)$ 的所有 不同的 子群。(提示： g 的某些幂生成相同的子群。)

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

因为我们还没有引入像拉格朗日定理这样的正式工具，所以我们手动进行了子群发现——尤其是在最后的练习中，我们尝试了 k 的几个值，看看它们生成哪些子群。 在下一章中，你将学习底层原理，这些原理允许你系统地确定子群的大小和生成器。

  • 原文链接： rareskills.io/post/multi...
  • 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～
点赞 0
收藏 0
分享
本文参与登链社区写作激励计划 ，好文好收益，欢迎正在阅读的你也加入。

0 条评论

请先 登录 后评论
RareSkills
RareSkills
https://www.rareskills.io/

RareSkills

如果觉得我的文章对您有用，请随意打赏。你的支持将鼓励我继续创作！