readme.md

title	tags
20. 环	zk abstract algebra ring theory ring

WTF zk 教程第 20 讲：环

在抽象代数中，环（Ring）是一种比群更复杂的代数结构。环包含了两个二元运算，通常表示为加法和乘法。这一讲，我们将介绍环的定义、分类和性质。

1. 环的定义

群是拥有一个运算的集合，而环是拥有两个二元运算的集合。它满足类似于整数加法和乘法的性质。环元素可以是整数或复数等数字，但也可以是多项式、函数和幂级数等非数字对象。

环的定义 一个环 $(R, +, \cdot)$ 包含了一个非空集合 $R$ 和两个二元运算 $+$（加法）和 $\cdot$（乘法），满足以下3条性质：

1. $(R, +)$ 为Abel群（交换群），即满足：

   • 加法封闭性： 对于任意 $a, b \in R$， $a + b \in R$。

   • 加法结合律： 对于任意 $a, b, c \in R$， $(a + b) + c = a + (b + c)$。

   • 加法单位元： 存在一个元素 $0 \in R$，对于任意 $a \in R$， $a + 0 = 0 + a = a$。

   • 加法逆元： 对于任意 $a \in R$，存在一个元素 $-a \in R$，使得 $a + (-a) = (-a) + a = 0$。

   • 加法交换律： 对于任意 $a,b \in R$， $a + b = b + a$。

2. $(R, \cdot)$ 为幺半群，即满足：

   • 乘法封闭性： 对于任意 $a, b \in R$， $a \cdot b \in R$。

   • 乘法结合律： 对于任意 $a, b, c \in R$， $(a \cdot b) \cdot c = a \cdot (b \cdot c)$。

   • 乘法单位元： 存在一个元素 $1 \in R$，对于任意 $a \in R$， $a \cdot 1 = 1 \cdot a = a$。

   有的书本中，环不需要有乘法单位元，与咱们的定义不同。咱们把不带乘法单位元的结构叫做伪环。

3. 乘法对于加法满足分配律，即对于任意 $a, b, c \in R$，有

   • $a \cdot (b + c) = a \cdot b + a \cdot c$
   • $(a + b) \cdot c = a \cdot c + b \cdot c$。

总的来说，环对加法群的要求比较高，要形成Abel群（群的4条基本性质 + 交换律）；而乘法群要求低一些，只需要满足群的3条性质，不需要每个元素存在乘法逆元；同时，乘法和加法需要满足分配律。

由于环比群更加具体，因此在环中，我们使用加法 $+$ 和乘法 $\cdot$ 代表环中的运算，而不是抽象的 🐔 和 🦆；加法单位元用 $0$ 表示；有时我们会把乘法符号省略，将 $a \cdot b$ 写为 $ab$。

下面介绍环中常用的符号：

符号	含义
$0$	加法单位元，也称零元
$-a$	元素 $a$ 的加法逆元
$a-b$	$a + (-b)$
$1$ 或 $e$	乘法单位元
$a^{-1}$	元素 $a$ 的乘法逆元
$ab$	$a \cdot b$
$\frac{a}{b}$ 或 $a/b$	$a \cdot b^{-1}$

2. 环的例子

我们以整数环和整数模n环为例，来熟悉什么是环。

2.1 整数环 $\mathbb{Z}$

大家最熟悉的环就是整数环，它由所有整数集合 $\mathbb{Z}$ 以及整数加法和乘法构成。

$$ ...,-5,-4,-3,-2,-1,0,1,2,3,4,5,... $$

我们验证它是否满足环的基本性质：

1. $(\mathbb{Z}, +)$ 为Abel群

2. $(\mathbb{Z}, \cdot)$ 存在单位元 $1$，封闭，且满足结合律。

3. 整数加法和乘法满足分配律。

因此，整数环 $(\mathbb{Z}, +, \cdot)$ 满足环的基本性质，构成环。

2.1 整数模n环 $\mathbb{Z}_n$

整数模n环也是密码学中常用的环，它由模n的剩余类以及模加法和乘法构成。

$$ 0,1,2,...,n-1 $$

我们验证它是否满足环的基本性质：

1. $(\mathbb{Z}_n, +)$ 为Abel群

2. $(\mathbb{Z}_n, \cdot)$ 存在单位元 $1$，封闭，且满足结合律。

3. 模加法和乘法满足分配律。

因此，整数模n环 $(\mathbb{Z}_n, +, \cdot)$ 满足环的基本性质，构成环。

3. 环的分类

3.1 零环

如果环 $(R, +, \cdot)$ 中只有一个元素，根据环的基本性质，这个元素就是加法单位元 $0$。这个环就是 $(0, +, \cdot)$，我们称之为零环。

我们也把零环称为平凡环，把除零环以外的环称为非平凡环。

3.2 交换环

如果环 $(R, +, \cdot)$ 中的乘法也满足交换律，即对于任意 $a, b \in R$，$ab = ba$，那么称该环为交换环。

我们在密码学常用环几乎都是交换环，比如整数环 $(\mathbb{Z}, +, \cdot)$，整数模 $n$ 环 $(\mathbb{Z}_n, +, \cdot)$，因此在本教程中，环默认指代交换环，除非特殊说明。

3.3 整环

首先，我们介绍零因子。对于环 $R$，如果存在非零元素 $a, b \in R$，使得 $ab = 0$ 成立，那么 $a$ 和 $b$ 被称为零因子。举个例子，在整数模6环 $Z_6$ 中，有 $2 \cdot 3 \equiv 0 \pmod{6}$，因此 $2$ 和 $3$ 为 $Z_6$ 的零因子。

若交换环 $R$ 中不存在零因子，那么我们称 $R$ 为整环。举个例子， $Z_5$ 是整环，任意两个非零元素相乘的结果不等于零。

3.4 域

域也是一种特殊的环。若交换环 $(R, +, \cdot)$ 的乘法群去除零元素后 $(R-\set{0}, \cdot)$ 能形成Abel群，那么我们称 $R$ 为域。例如 $Z_5$ 去除零元素后为 $Z_5^* $，而 $(Z_5^* , \cdot)$ 满足Abel群性质，因此 $Z_5^* $。

域在密码学和零知识证明中非常重要，我们之后会有一讲专门介绍它。

4. 环的基本性质

下面，我们介绍一些环的基本性质。

性质1. 加法单位元 $0$ 唯一。

点我展开证明👀

设零元素为0，若存在另一元素0'也满足加法单位元的性质，则有：

$0 + 0' = 0'$

$0 + 0' = 0$

因此有 $0 = 0'$，即零元素唯一。

性质2. 元素的加法逆元唯一。

点我展开证明👀

对于任意元素 $a$，设其加法逆元为 $b$ 和 $c$。则有：

$a + b = 0$

$a + c = 0$

两式相减得 $b - c = 0$，即 $b = c$。所以， $a$ 的加法逆元唯一。

性质3. 乘法单位元 $1$ 唯一。

性质4. 元素的零乘性质： 对于任意元素 $a$，有 $a \cdot 0 = 0 \cdot a = 0$，即 $0$ 是乘法的吸收元素。

点我展开证明👀

对于零元，有 $0 = 0 + 0$，因此对于任意元素 $a$，有 $a \cdot 0 = a \cdot (0+0) = a \cdot 0 + a \cdot 0$，两式相减得 $a \cdot 0 = 0$。

$0 \cdot a = 0$ 可用相同方法证明。证毕

性质5. 非平凡环（非零环）中，加法单位元和乘法单位元不相等，即 $0 \neq 1$。

点我展开证明👀

假设加法单位元和乘法单位元相等，则对于环中任意元素 $a$，有 $a = a \cdot 1 = a \cdot 0 = 0$，也就是任意元素 $a = 0$，该环是零环/平凡环，与条件矛盾。因此非平凡环（非零环）中，加法单位元和乘法单位元不相等。证毕。

性质6. 元素 $a$ 和 $b$ 为环 $R$ 中的元素，有 $(-a)b = -(ab) = a(-b)$。

点我展开证明👀

首先，先证明 $(-a)b = -(ab)$，其实就是证明 $ab$ 和 $(-a)b$ 互为逆元。根据分配率，有 $(-a)b +ab = (-a + a)b= 0b = 0$，因此 $ab$ 和 $(-a)b$ 互为逆元，有 $(-a)b = -(ab)$ 成立。

我们可以用同样的方法证明 $ab$ 和 $a(-b)$ 互为逆元，因此 $-(ab) = a(-b)$。

因此，有 $(-a)b = -(ab) = a(-b)$。证毕。

性质7. 元素 $a$ 和 $b$ 为环 $R$ 中的元素，有 $(-a)b = -(ab) = a(-b) = - (-a)(-b)$。

点我展开证明👀

首先，先证明 $(-a)b = -(ab)$，其实就是证明 $ab$ 和 $(-a)b$ 互为逆元。根据分配率，有 $(-a)b +ab = (-a + a)b= 0b = 0$，因此 $ab$ 和 $(-a)b$ 互为逆元，有 $(-a)b = -(ab)$ 成立。

我们可以用同样的方法证明 $ab$ 和 $a(-b)$ 互为逆元，因此 $-(ab) = a(-b)$。

接下来，我们证明 $-(ab) = - (-a)(-b)$，也就是 $-ab$ 和 $(-a)(-b)$ 互为逆元。根据分配率，有 $-ab + (-a)(-b)$ = -a(b-b) = -a0= 0$，因此它们互为逆元，有 $-(ab) = - (-a)(-b)$ 成立。

因此，有 $(-a)b = -(ab) = a(-b) = - (-a)(-b)$。证毕。

大家可以以整数环和整数模n环为例，理解这些性质。

5. 子环

对于环 $(R, +, \cdot)$，如果 $S$ 是 $R$ 的非空子集，且 $S, +, \cdot$ 也是环，那么我们称 $S$ 为 $R$ 的子环。

我们可以用以下条件判断环 $S$ 是否为 $R$ 的子环：

1. 加法封闭： 对于任意 $a, b \in S$，有 $a+b \in S$。
2. 零元的保持： $R$ 的零元也在 $S$ 中，即 $0_R = 0_S$。
3. 加法逆元存在： 对于任意 $a \in S$，有 $-a \in S$。
4. 乘法封闭： 对于任意 $a,b \in S$，有 $ab \in S$。
5. （乘法）单位元存在： $S$ 存在乘法单位元。

或者等价的：

1. 减法封闭（判断子群的条件）： 对于任意 $a, b \in S$，有 $a+b \in S$。
2. 乘法封闭： 对于任意 $a,b \in S$，有 $ab \in S$。
3. （乘法）单位元存在： $S$ 存在乘法单位元。

6. 总结

这一讲，我们介绍了环的基本定义和性质，了解了环的一些例子。环是抽象代数中的一个重要概念，为后续学习提供了基础。