有限域中的单位根

本文解释了有限域中的单位根是什么，以及它们是如何与乘法子群相互关联的。读者应该熟悉之前关于循环群基本定理的章节。

该定理指出，给定一个阶为 的乘法群 ，当 能整除 时，存在一个唯一的阶为 的子群。否则，如果 不能整除 ，则不存在阶为 的子群。

它还指出，如果 是 的一个生成元，那么 生成阶为 的子群。

在本文中，我们将展示这个子群的所有元素都是所谓的 -次单位根，并且生成元 就是所谓的本原 -次单位根。

本章的动机和目标

在有限域中，计算 的平方根很容易：它们是同余于 和负 (即 和 ) 的数字。记住，在域 中，数字 与 同余)。换句话说，。这个集合是方程 的解集，其中 是有限域的一个元素。

但是，如果我们想要计算 的立方根，或者更一般地，-th 根呢？根据定义，-th 单位根是满足方程 的元素。但是我们如何找到它们呢？

我们可以逐个尝试所有元素——一种强力方法——但当字段包含许多元素时，这是不可行的。幸运的是，有一种简单的方法可以找到它们。在有限域 中，-th 单位根恰好是阶为 的乘法子群的元素。 这个定义假设 能整除

在关于循环群基本理论的文章中，我们学习了如何找到阶为 的乘法子群的所有元素。首先，我们从乘法群 的生成元中获得该子群的生成元。然后，使用此生成元，我们可以找到阶为 的子群的所有元素。

因此，如果 能整除 ，找到 的 -th 单位根与找到阶为 的乘法子群没有区别，我们已经知道如何做到这一点。

我们本章的目标是证明这种等价性——如果 能整除 ，所有 -th 单位根的群与阶为 的乘法子群之间的等价性。

为此，我们需要证明以下两个陈述：

1. 阶数为 的乘法子群中的每个元素 满足 。
2. 假设 能整除 。那么， 中满足 的每个元素 都属于唯一的阶数为 的子群。

我们将通过示例来探索这两个陈述，以说明它们是正确的。由于正式的证明在数学上可能有些苛刻，我们将把其中的一些推迟到附录中，供感兴趣的读者参考。

1. 阶数为 的子群中的每个元素 满足

第一个陈述表明，阶数为 的乘法子群的所有元素都是 -th 单位根。

但是，这不足以建立所有 -th 单位根的群与阶数为 的乘法子群之间的等价性（当 能整除 时），因为它不能保证所有 -th 单位根都属于该子群——这将在陈述 2 中讨论。

我们将从证明该陈述开始本节，然后通过示例表明该陈述成立。

陈述 1 的证明

从关于循环群基本定理的文章中回想一下，阶数为 的唯一子群由 生成，其中 是乘法群 的生成元。我们将 称为通过取 模 的连续幂生成的元素：

设 是 中任意元素，对于某个 。目标是证明 。

下面的证明假设生成器具有属性 ；有关此事实的证明，请参见附录 A。

让我们计算 如下：

因此，当 raised 到 power 时，阶数为 的子群中的每个元素 等于 1。

中陈述 1 的示例

在这个例子中，我们有 。此外，元素 是乘法群 的一个生成元。

_如何在本文中不介绍如何找到乘法群的生成元，但是 galois 库提供了一种快速的方法。给定字段 ，一种找到生成元的方法是使用 primitive_element 属性，如下所示。_

import galois
GF = galois.GF(7) # 定义域
GF.primitive_element # GF(3, order=7)

阶数为 3 的子群

由于 3 可以整除 ，循环群基本定理保证存在一个唯一的阶数为 3 的子群。

该子群由 生成。因此，

现在，我们要验证 中每个元素 满足 。下面是实现的：

所以，元素 和 满足 。因此，条件满足。

阶数为 2 的子群

由于 2 可以整除 ，循环群基本定理保证存在一个唯一的阶数为 2 的子群。

该子群由 生成。因此，

现在，我们要验证 中每个元素 满足 。

所以，元素 和 满足 。因此，条件满足。

练习。 验证 中每个元素 满足 。

2. 如果 能整除 ，那么 中每个满足 的元素 都属于唯一的阶数为 的子群

这个陈述断言，如果 能整除 ，则所有 -th 单位根都属于阶数为 的乘法子群。

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

在继续之前，让我们考虑 不能整除 的情况。在这种情况下，循环群基本定理告诉我们不存在阶数为 的子群，因此不存在等价性。

中的示例

在这个例子中，我们有 。此外，元素 是乘法群 的一个生成元。

阶数为 的子群

由于 3 能整除 ，因此存在一个唯一的阶数为 3 的子群。该子群由 生成。因此，

我们想要验证 中满足 的每个元素 都属于 中这个唯一的阶数为 的子群。让我们找到 中所有这样的元素 ，如下所示：

元素 和 满足 。这三个元素恰好是 中阶数为 的子群的成员。因此， 中每个满足 的元素 都属于唯一的阶数为 的子群。

练习。 验证 中每个满足 的元素 都属于唯一的阶数为 的子群。

中的示例

在这个例子中，我们有 。此外，元素 是乘法群 的一个生成元，可以使用 galois 库进行验证：

GF = galois.GF(17) # 定义域
GF.primitive_element # GF(3, order=17)

阶数为 的子群

由于 4 能整除 ，因此存在一个唯一的阶数为 4 的子群。该子群由 生成。因此，

我们想要验证 中满足 的每个元素 都属于 中这个唯一的阶数为 的子群。让我们找到 中所有这样的元素 ，如下所示：

元素 和 满足 。这四个元素恰好是 中阶数为 的子群的成员。因此， 中每个满足 的元素 都属于唯一的阶数为 的子群。

练习。 验证 中每个满足 的元素 都属于唯一的阶数为 的子群。

本原 -次单位根

本原 -次单位根是一个特殊的 -次单位根：它是一个 -次单位根，可以生成所有其他的 -次单位根。

由于我们感兴趣的 -次单位根的群与阶数为 的子群相同，因此本原 -次单位根恰好是该子群的生成元。

注意：在 不能整除 的情况下（考虑到有限域），可能仍然存在 -次单位根，但在这种情况下，没有本原 -次单位根。

因此，找到本原 -次单位根非常简单：它与找到阶数为 的子群的生成元相同，循环群基本定理告诉我们如何做到这一点。

-th 单位根的正式定义是具有阶数 的 -th 单位根，其中元素 的阶数 是大于零的最小正整数 ，使得 。

例如， 是 中的 6th 单位根，因为 ，但它不是本原的 6th 根，因为有一个小于 6 的幂会使其为 ，特别是 3，即 。

本原 -次单位根的数量

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

本原 -次单位根（和生成元）的数量由Euler总计函数 给出。该事实的证明超出了本文的范围。对于我们正在考虑的应用——数论变换——我们只需要一个本原 -次单位根，可以使用基本定理找到它，假设我们知道 的生成元。

在本章的剩余部分，我们将展示示例，说明如何使用基本定理找到本原 -次单位根，然后为给定的 找到所有 -次单位根。

中 4 次单位根的示例

乘法群 的生成元是元素 ，可以使用 galois 库找到它。

然后，阶数为 4 的子群的生成元为 。

根据我们的讨论，此生成元是本原 4 次单位根。让我们使用本原 -次单位根的定义来检查一下。我们需要证明：

1. 元素 是 4 次单位根。这可以通过检查 来看出。
2. 元素 的阶数为 4。这意味着 4 是最小的正整数 ，使得 。让我们在下面检查一下：

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

中 8 次单位根的示例

由于 是乘法群 的生成元，因此阶数为 的子群的生成元为 。

让我们检查一下它是否也是本原 8 次单位根。我们需要检查：

1. 元素 是 8 次单位根。这可以通过检查 来看出。
2. 元素 的阶数为 8。这意味着 8 是最小的正整数 ，使得 。让我们在下面检查一下：

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

练习。 找到 中的本原 2 次单位根和所有 2 次单位根的子群。

结论和总结

需要一种有效的方法来找到所有 -次单位根，这正是我们在本文中研究的内容。总之，我们确定：

• 如果 ，则有限域 的元素 是 -次单位根。
• 如果 能整除 ，那么包含所有 -次单位根的 的子群是由循环群基本定理保证的唯一的阶数为 的子群。
• 本原 -次单位根生成所有 -次单位根的子群。如果 是乘法群 的生成元，并且 能整除 ，那么元素 是本原 -次单位根。

附录 A

阶数为 的子群的生成元 满足 ：

设 是乘法群 的一个生成元。从循环群基本定理中回想一下，元素 生成唯一的阶数为 的子群。我们的目标是证明 。

证明。 费马小定理指出，如果 是一个质数，那么对于任何整数 ：

例如，如果 且 ，则 。

如果 不能被 整除，我们可以将上面等式的两边都除以 。这表明费马小定理等价于以下陈述：

我们现在计算 如下：

附录 B

如果 且 ，则 是阶数为 的唯一循环子群的成员。

设 是 的一个生成元。这等价于 表示 是 -th 单位根。

设 是阶数为 的乘法子群的生成元（ 直接来自循环群基本定理）。

如果 且 那么我们必须证明存在一个整数 使得 。 中的整数 的存在证明了 可以由 生成，因此是阶数为 的唯一子群的一部分。

为了找到这样的 ，我们将 替换为 并将 替换为 ，将 转换为：

我们能想出一个使方程成立的 吗？如果我们有策略地选择一个 使得指数 将抵消并留下：

将 插入此方程的左侧，我们得到

我们可以看到 和 项抵消，留下 。

我们可以将原始定义替换为 ， 和 ，并看到

因此，如果 ，那么确实存在一个 使得 。 只是

其中 是 的解， 是子群的阶数， 是我们有限域的模数。

但是，我们仍然必须证明 是一个整数，因为通过将 提高到分数来生成一个值不符合作为生成的子群的成员。

显示 是一个整数

为了证明 是一个整数，我们需要证明除以 没有余数。

当我们进行除法时，我们应该得到一个商 和一个余数 。我们要证明 必须为 0。

余数不能大于除数（例如， 不能有余数 5 或更大），因此我们还有以下条件：

我们可以通过将其从 被除数 / 除数 = 商 + 余数 的形式转换为 被除数 = 商⋅除数 + 余数 来隔离 （为了说明此重写，请考虑 6/4=1，余数 2 可以写成 6 = 4⋅1 + 2）。在重写的形式中，我们有：

为了证明 , 我们将暂时搁置 , 并推导出 的另一个属性。

事实：

可以从以下事实推导出来：

所以通过替换，通过 power of a power rule，。

替换 到

我们现在有足够的工具来证明 中的 remainder 为零。我们提醒读者 因为 是本原 -次单位根。

我们现在证明使用定义

足以表明 ：

由于 是本原 -th 单位根，因此只有两个解 ：

回想一下 被定义为

我们知道任何有效的除法 都不能导致余数 大于等于 , 具体来说，余数必须在范围内 。范围限制 意味着 。

因此，排除 的可能性，唯一解 是 (即 )。

由于 , 将 除以 的结果是一个整数。

最后，由于 定义为 是一个整数。

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