密码学基础：环论(Rings)

这是关于加密技术的一系列文章的一部分。如果这是你接触到的第一篇文章，我强烈建议你从系列的开头开始阅读。

这个系列已经是一段相当漫长的旅程——我们快要结束它了。几个月前，我们开始讨论群，然后通过探索哈希函数、多项式、配对和有限域迅速扩展了我们基础知识。

我想我实际上从来没有深入讲解有限域。请原谅我的疏忽！

这些是我们在这一系列中基于的每一个方法和技术的数学基础。

然而，有一个结构我们一直避免谈论。在这之前谈论它感觉不对，因为它是最复杂的一个。但到现在为止我们已经覆盖了一些非常复杂的主题——所以，是的，我们现在准备好了。我相信时机是对的。

让我们谈谈 环 。

放松一点，伙计。

为什么要环？

环 是大多数 后量子密码学（PQC）方法的基础结构。我们的目标是首先定义什么是环，并理解一些基本概念，这样我们在后续讨论中可以更自然地理解我们探索的_PQC_方法。

这些与我们在环签名中提到的环完全不同。在那个例子中，名字只是一种隐喻，试图表示构造的循环性质。

我们现在要进入抽象代数的领域——这是真的。

系好安全带，让我们出发吧！

环

一个环是一个抽象代数结构，就像群一样。正如你所记得，一个群是由一个_集合_和一个_运算_定义的。我们看到这样一个简单的结构有许多用途，特别是因为某些特定的属性，例如存在_生成元_和子群。

类似地，_环_的定义也很简单。但简单的定义可能会掩盖将来的复杂性。确实，我们需要考虑更多的内容。

不再多说，这里是定义：一个_环是一个三元组(R, +, ⋅)——因此，现在需要考虑的元素有三个，而不是两个，其中_R_是一个非空集合，关联着两个_R_上的二元运算。

这些运算需要满足几个条件。

加法

首先，_R_必须在运算+下表现得像一个阿贝尔群（我们通常称之为加法）。这意味着：

• 必须满足结合律，即(a + b) + c = a + (b + c)，
• 必须满足交换律，即a + b = b + a，
• 必须存在一个单位元素 e，使得a + e = a，
• 必须存在一个加法逆元，即a + (-a) = e。

如果我们想象一下，如果第二个运算( ⋅)不存在，我们所剩下的只有一个群——一个我们相当熟悉的结构。最有趣的部分接下来会出现。

乘法

第二个运算通常称为乘法。集合_R_必须在这一运算下是一个幺半群。

什么？

幺半群。是的。在乘法下表现得像一个幺半群意味着：

• 满足结合律，即(a ⋅ b) ⋅ c = a ⋅ (b ⋅ c)，
• 必须存在一个单位元素 e’，使得a ⋅ e’ = e’ ⋅ a = a。

花哨的词，比较简单的意义。

现在我们有了两个运算，我们还需要考虑它们如何叠加——所以，出现了一个额外的条件：乘法必须对加法进行分配。这简单地意味着：

• a ⋅ (b + c) = (a ⋅ b) + (a ⋅ c)
• (b + c) ⋅ a = (b ⋅ a) + (c ⋅ a)

注意顺序保持。乘法可能不是交换的！

最后，还有隐含的_封闭性_要求，意味着任何二元运算的组合的结果必须位于集合_R_中。

环的例子

有了这些定义，你可能会想环可能并不是那么常见。实际上，正好相反——它们实际上是无处不在！

例如，_模q的整数_表现得像一个环。当然，当 q 是素数时，我们知道它们也像一个域一样。但是在更一般的情况下，它们总是表现得像一个环。

事实上，整数（不能是模_q_的！）也表现得像一个环。还有 有理数 。实数、复数，以及四元数。等等……_所有的东西_都是一个环吗？

例如，无理数 并不是。并不是所有东西都是一个环！

我们还可以想出更丰富的例子。

带有_域_中元素的 方阵 也构成一个环。实际上，这是其中一个_不满足交换律_的例子。尽管如此，它们仍然构成一个环——一个 非交换环 。

重要的一个

你问我们为什么关心环？嗯，我们需要了解一个非常重要的环，作为一些_PQC_方法的基础。你已经在这个系列中听说过它们很多次。它们现在应该是老朋友了。

你能猜到它们是什么吗？

没错——多项式！

兄弟，它们无处不在。总是该死的多项式。

我们将看到它们在接下来的内容中的应用。我们的旅程需要我们暂时放下它们，这样我们可以讨论一些关于环的一般内容。

定义

当我们看到群时，我们看到可能存在子群。我们还看到了群同态。当然，_环_也有这些类型的结构和属性：我们可以定义_子环_和环同态。但还有一些额外的定义是这一结构所特有的。我们需要特别了解一个：理想。

理想( Ideals )

在这里我们不能与群做任何类比，因此这将是一个全新的概念！

给定一个环R，我们可以定义_左理想_和右理想。我们之所以称为_左_和_右_是因为交换的原因，正如我们在片刻后会看到。

一个_R_的_左理想_是_R_的非空子集I，使得对于_I_中的每个元素x, y，以及_R_中的每个元素r，元素_x + y_和_r ⋅ x_也在_I_中。是的。

数学符号可能会有所帮助：

或许没有。我不知道。

我想问题是为什么。到底我们为什么要关心定义这些“理想”的东西，它们会有什么扭曲的应用？

这样想：_I_是_R_的某个子集，某种程度上在_R_上进行操作，并将其_缩减_至理想——因此它以某种方式像一个模运算。

别太担心，稍后我们将更加清楚它是如何有用的！

为了完整性，我们还将定义一个右理想，它与左理想非常相似——只不过_(x ⋅ r)需要在理想中，而不是(r ⋅ x)_——因此得名！

一个例子

让我们分析整数环ℤ。我们声称所有_q_的倍数的集合是双侧理想（意味着它既是_左_理想又是_右_理想）_ℤ的一个理想。让我们用(q)_表示它。

在整数的情况下，交换律成立，因此这确实是一个双侧理想。

检查这是否为真，可以通过评估理想定义中的条件。这些条件是：

• 在_(q)中添加元素将导致产生(q)_中的元素，因此该集合在加法下是_封闭_的。

• 将任何在_(q)中的元素乘以某个整数将出现另一个在(q)_中的元素：

因此，_(q)_确实是_ℤ_的一个双侧理想。其实没那么可怕，对吧？

还有其他一些定义待探讨——例如，环的特征是什么，或者核在环同态中是什么。但我认为专注于我们需要更好地理解密码学方法的内容会更有意义。我将把这些定义留给你去查看。现在让我们进入正题。

商环( Quotient Rings)

我们即将进入一些模糊的水域，但这正是我们理解 PQC 方法所需的真正 调味品 。

商环，也被称为 因子环、差环 或 余数类环 ，是一种用 理想 派生的环。这也是理想为什么重要的部分原因。

给定一个环 R 和一个 双侧 理想 I ，商环 R / I 是其元素为 I 在 R 中的 余类 的环。

哈？

这是……? 让我们试图理解这些。

为此，我们必须首先理解什么是 等价类 。

等价关系和类

继续进行，注意这些熟悉的例子，让我们关注模_q_的整数。在这种情况下，让我们将其视为一个 环，例如：

我保证这个符号在一会儿会更有意义！

在我们对群的介绍中，我们看到模运算用于将任何在此集合外的整数映射到此集合中。因此当我们有这样的东西时：

我们可以自然地认为 a 和 b 是 等价 的。等价可以通过任何类型的关系来给出，不仅仅是通过模运算定义的关系。任何这样的关系可以写作 a ~ b ，这意味着 a 与 b 是等价的。

一个等价关系有一个更正式的定义，涉及集合的笛卡尔积和一些奇怪命名的属性（反射性、对称性和传递性）。但我们并不太关心这些——只了解大致概念就可以了。

在模_q_的整数中，任何形如 a = k.q + b 的数都将与 b 等价——并且这样的整数有无穷多个！

我们可以将所有这些等价的整数分组成一个集合。这样的集合被称为等价类。实际上，我们的_模_q_的整数环中的每个元素代表的不仅仅是单一的值——它是_整个等价类_的代表。当我们在商环的定义中提到_余类_时，我们指的就是这些等价类。

如果你想一想，模_q_的整数允许我们将一个“更大的”环——整数环，缩小到一个较小的环，通过提供一种将每个整数映射到其等价值的方式。这是重要的一点！

计算商环

有了等价类，就更容易理解商环。继续我们的例子，让我们取环_ℤ和双侧理想(q)_。

计划是这样的：首先定义一个等价关系：

简单而言：两个元素是等价的，如果它们的差是_q_的倍数。既然我们有了等价关系，我们也有一个_等价类——_所有与_a_等价的元素是：

这样的类有多少？好吧，我们从_0_开始计数！等价类将是：

我们可以对_1_进行同样的操作：

事实上，我们可以对所有整数进行操作，直到q - 1。当我们到达_q_时，有趣的事情发生了：

啊哈！我们碰巧发现了一个已经存在的类！因此，商环_ℤ/(q)仅仅是：

取每个等价类的_单一代表_即可得：

等等……我们之前见过那个！它是模_q的整数环！你看看这个。一切混乱只是为了达到这个。我发誓，有时数学是如此复杂……

在某种程度上，就像我们对整数执行了_模_运算，再对模_q的整数执行了_模_运算。这就是我们使用符号_ℤ/qℤ_的原因。

重温定义

这里有必要提出我们例子的最终形式化定义，来结束这一部分。环_R_与双侧理想_I_的商可以通过以下过程获得：

• 定义等价关系：

• 找到所有形如的等价类：

商环_R/I_将简单地是所有这样类的集合。希望最初的定义现在更易理解：

给定一个环_R_和一个双侧理想I，商环_R / I_是其元素为_I_在_R_中的余类的环。

商多项式环

之前，我提到过 商环 对 PQC 很重要。当我这样说时，我没有提到的是，我们的兴趣特别在于 多项式商环。

此时，更容易想象它们为什么重要——它们提供了一种将 多项式（它们形成一个环）映射到一个_较小的环_的方法，就像模运算一样。

而且，这种能力对我们在这个系列中介绍的大部分方法的开发至关重要！所以，是的，这可能是相当重要的！

让我们慢慢来理解。

来杯茶吧。

我们将从一个在_有限域_上的多项式环开始。我们将其表示为 𝔽[X] 。这样的域可以是例如_模q的整数——系数可以使用模运算来降低。目前，一切都很好！

接下来，我们将需要 𝔽[X] 的一个双侧理想。事实证明，我们可以通过选择某个多项式 f(X) 在 𝔽[X] 中，并将理想设置为 所有它的倍数 的集合来构建一个理想。

该环中的任何多项式显然都可以被_f(X)_整除。因此很容易检查它确实是一个理想！

再次，我们定义一个等价类——两个多项式在其差是 f(X) 的倍数时是 等价 的：

最后，我们找到在该关系下的所有不同等价类。这可能更难以想象，但概念是，任何对多项式 by f(X) 进行除法的可能余数都将位于_商环_中，表示为 𝔽[X]/(f(X)) 。

余数的次数不得高于 f(X) 。因此，由于我们在 有限域 上工作，我们有 有界系数，而且由于我们在工作于多项式商中，我们有 有界次数 。

总之：我们已经找到了一种将几乎任何_整数值多项式_映射到_有限多项式集_的方法！太棒了！

正如我们将看到的，这对_PQC_方法非常有用。

一个实际例子

为了巩固这个想法，让我们看一个简单的例子。假设我们选择_模数多项式_为f(X) = X² + 1，并将我们的有限域设置为𝔽₇。

多项式_f(X)_将用于将高次多项式.reduce_to a bounded degree。就比如，我们选择多项式P(X) = X⁵ - 3X² + 6。

对_P(X)_除_f(X)_会得到一个_商_和一个余数：

我们需要关注余数（就像模运算一样！）。当然，既然我们在有限域中工作，我们需要对_R(X)_进行模_7_的运算。这产生了：

这样，我们就将原始_P(X)_模f(X)。并且有_P(X)_等价于R(X)：

任何对_f(X)_的余数是_R(X)_的多项式，将会被等价于R(X)！因此，它在商环_𝔽₇[X]/(X² + 1)_中由元素_R(X)_来表示。

总结

哇，这是我想象的时间要长得多。

正如你可能注意到的，_环_需要比_群_更高程度的_抽象_才能完全理解。这就是为什么它们没有在系列前面引入——我们正在逐步提高复杂性。

好吧……“逐步”。此时什么都不慢了！

这篇文章的主要收获，除了某些新的抽象概念，就是_商多项式环_的概念。如前所述，它们是我们继续进行一些_PQC_方法（除了格，我们将在下一部分中讨论）的缺失基础。

剩下的就是时候_去进行后量子计算_了。但是要提出任何_PQC_方法，我们需要的不仅仅是一个数学结构——我们需要一个_困难的问题_来解决。环也有其中的一些，就如我们将在下次看到的那样！

• 原文链接： medium.com/@francomangon...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，在这里修改，还请包涵～