Skip to content

Latest commit

 

History

History
230 lines (128 loc) · 9.11 KB

readme.md

File metadata and controls

230 lines (128 loc) · 9.11 KB
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. 总结

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