Skip to content

Files

Latest commit

25da7fc · May 4, 2024

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 , + , ) 包含了一个非空集合 R 和两个二元运算 + (加法)和 (乘法),满足以下3条性质:

  1. ( R , + ) 为Abel群(交换群),即满足:

    • 加法封闭性: 对于任意 a , b R a + b R

    • 加法结合律: 对于任意 a , b , c R ( a + b ) + c = a + ( b + c )

    • 加法单位元: 存在一个元素 0 R ,对于任意 a R a + 0 = 0 + a = a

    • 加法逆元: 对于任意 a R ,存在一个元素 a R ,使得 a + ( a ) = ( a ) + a = 0

    • 加法交换律: 对于任意 a , b R a + b = b + a

  2. ( R , ) 为幺半群,即满足:

    • 乘法封闭性: 对于任意 a , b R a b R

    • 乘法结合律: 对于任意 a , b , c R ( a b ) c = a ( b c )

    • 乘法单位元: 存在一个元素 1 R ,对于任意 a R a 1 = 1 a = a

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

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

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

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

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

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

符号 含义
0 加法单位元,也称零元
a 元素 a 的加法逆元
a b a + ( b )
1 e 乘法单位元
a 1 元素 a 的乘法逆元
a b a b
a b a / b a b 1

2. 环的例子

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

2.1 整数环 Z

大家最熟悉的环就是整数环,它由所有整数集合 Z 以及整数加法和乘法构成。

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

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

  1. ( Z , + ) 为Abel群

  2. ( Z , ) 存在单位元 1 ,封闭,且满足结合律。

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

因此,整数环 ( Z , + , ) 满足环的基本性质,构成环。

2.1 整数模n环 Z n

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

0 , 1 , 2 , . . . , n 1

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

  1. ( Z n , + ) 为Abel群

  2. ( Z n , ) 存在单位元 1 ,封闭,且满足结合律。

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

因此,整数模n环 ( Z n , + , ) 满足环的基本性质,构成环。

3. 环的分类

3.1 零环

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

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

3.2 交换环

如果环 ( R , + , ) 中的乘法也满足交换律,即对于任意 a , b R a b = b a ,那么称该环为交换环

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

3.3 整环

首先,我们介绍零因子。对于环 R ,如果存在非零元素 a , b R ,使得 a b = 0 成立,那么 a b 被称为零因子。举个例子,在整数模6环 Z 6 中,有 2 3 0 ( mod 6 ) ,因此 2 3 Z 6 的零因子。

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

3.4 域

域也是一种特殊的环。若交换环 ( R , + , ) 的乘法群去除零元素后 ( R { 0 } , ) 能形成Abel群,那么我们称 R 为域。例如 Z 5 去除零元素后为 Z 5 ,而 ( Z 5 , ) 满足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 0 = 0 a = 0 ,即 0 是乘法的吸收元素。

点我展开证明👀

对于零元,有 0 = 0 + 0 ,因此对于任意元素 a ,有 a 0 = a ( 0 + 0 ) = a 0 + a 0 ,两式相减得 a 0 = 0

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

性质5. 非平凡环(非零环)中,加法单位元和乘法单位元不相等,即 0 1

点我展开证明👀

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

性质6. 元素 a b 为环 R 中的元素,有 ( a ) b = ( a b ) = a ( b )

点我展开证明👀

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

我们可以用同样的方法证明 a b a ( b ) 互为逆元,因此 ( a b ) = a ( b )

因此,有 ( a ) b = ( a b ) = a ( b ) 。证毕。

性质7. 元素 a b 为环 R 中的元素,有 ( a ) b = ( a b ) = a ( b ) = ( a ) ( b )

点我展开证明👀

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

我们可以用同样的方法证明 a b a ( b ) 互为逆元,因此 ( a b ) = a ( b )

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

因此,有 ( a ) b = ( a b ) = a ( b ) = ( a ) ( b ) 。证毕。

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

5. 子环

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

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

  1. 加法封闭: 对于任意 a , b S ,有 a + b S
  2. 零元的保持: R 的零元也在 S 中,即 0 R = 0 S
  3. 加法逆元存在: 对于任意 a S ,有 a S
  4. 乘法封闭: 对于任意 a , b S ,有 a b S
  5. (乘法)单位元存在: S 存在乘法单位元。

或者等价的:

  1. 减法封闭(判断子群的条件): 对于任意 a , b S ,有 a + b S
  2. 乘法封闭: 对于任意 a , b S ,有 a b S
  3. (乘法)单位元存在: S 存在乘法单位元。

6. 总结

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