Skip to content

Latest commit

 

History

History
102 lines (57 loc) · 4.57 KB

readme.md

File metadata and controls

102 lines (57 loc) · 4.57 KB
title tags
16. Abel群
zk
abstract algebra
group theory
abelian group

WTF zk教程第16讲:Abel群

这一讲,我们将介绍一类在密码学中常用的群:Abel群,它的特点就是满足交换律。

1. Abel 群

Abel群除了满足4条群的基本性质之外,还需要满足交换律。若群 $(G, 🐔)$ 满足下列 5 个性质,则我们称 $G$ 为 Abel群:

  1. 封闭性: 对于任意 $a, b \in G$,有 $a 🐔 b \in G$
  2. 结合律: 对于任意 $a, b, c \in G$,有 $(a 🐔 b) 🐔 c = a 🐔 (b 🐔 c)$
  3. 单位元: 存在一个元素 $e \in G$,对于任意 $a \in G$,有 $a 🐔 e = e 🐔 a = a$
  4. 逆元: 对于任意 $a \in G$,存在一个元素 $b \in G$,使得 $a 🐔 b = b 🐔 a = e$,其中 $e$ 是单位元。
  5. 交换律: 对于任意 $a, b \in G$,有 $a 🐔 b = b 🐔 a$

因此,Abel就是满足交换律的群。由于加法、乘法运算都满足交换律,所以很多常见群都属于Abel群,包括:

  1. 整数加法群 $(\mathbb{Z}, +)$,因为 $a + b = b+a$

  2. 整数去0乘法群 $(\mathbb{Z}, \times)$,因为 $ab = ba$

  3. 整数模n加法群 $(\mathbb{Z}_n, +)$,因为 $a + b \equiv b+a \pmod{n}$

  4. 整数模n乘法群 $(\mathbb{Z}_n^*, \times)$,因为 $ab \equiv ba \pmod{n}$

2. Abel 群的性质

这一节,我们介绍Abel群的一些性质,并且将子群、正规子群、商群、同态的知识点复习一遍。

1. 群 $(G, 🐔)$ 为Abel群,当且仅当对于任意 $a,b \in G$,有 $(a🐔b)^2 = a^2🐔b^2$

点我展开证明👀

我们要证明群 $(G, 🐔)$ 满足交换律。对于任意 $a,b \in G$$(a🐔b)^2 = a🐔b🐔a🐔b$

$(a🐔b)^2 = a^2🐔b^2$ 可以写成 $a🐔b🐔a🐔b = a🐔a🐔b🐔b$,两边分别消去最左边的 $a$ 和最右边的 $b$,有 $b🐔a = a🐔b$,因此交换律成立,群 $(G, 🐔)$ 是Abel群。证毕。

$(\mathbb{Z}, \times)$ 为例,有 $(2 \times 3)^2 = 2^2 \times 3^2 = 36$

2. 群 $(G, 🐔)$ 为Abel群,对于任意 $a,b \in G$,有 $(a🐔b)^n = a^n🐔b^n$

点我展开证明👀

$(G, 🐔)$ 为Abel群,$(a🐔b)^n = a🐔b🐔...🐔a🐔b = a🐔a🐔...🐔b🐔b = a^n🐔b^n$。证毕。

$(\mathbb{Z}, \times)$ 为例,有 $(2 \times 3)^n = 2^n \times 3^n$

3. Abel群的子群也是Abel群。

点我展开证明👀

$(G, 🐔)$ 为Abel群,群 $H$$G$ 的子群。对于任意 $a, b \in H$,有 $a, b \in G$,因此有有 $a 🐔 b = b 🐔 a$。所以群 $H$ 也是Abel群。证毕。

$(\mathbb{Z}, +)$ 为例,偶数加法群是它的子群,并且它也是Abel群,满足交换律。

4. 群 $(G, 🐔)$ 为Abel群,对于整数n, $G$ 中每个元素的 $n$ 次方构成的群 $G^n$$G$ 的子群, $G^n = \set{a^n \mid a \in G}$

点我展开证明👀

$(G, 🐔)$ 为Abel群,对于任意 $a, b \in G$,有 $a^n, b^n \in G^n$。有 $a^n (b^n)^{-1} = a^n (b^{-1})^{n} = (ab^{-1})^n$。根据封闭性, $ab^{-1} \in G$,因此 $(ab^{-1})^n \in G$,因此群 $G^n$$G$ 的子群。证毕。

$(\mathbb{Z}, \times)$ 为例,所有整数的平方构成的群 $\set{1, 4, 9, ...}$ 是它的子群。再以 $(\mathbb{Z}_5^*, \times)$ 为例,所有元素的平方构成的集合 $(\mathbb{Z}_5^*)^2 = \set{1^2, 2^2, 3^2, 4^2} = \set{1,4,4,1} = \set{1,4}$ 是它的子群。这个性质对于我们之后理解二次方剩余很有帮助。

5. Abel群的子群均是正规子群。

点我展开证明👀

设群 $(G, 🐔)$ 为Abel群,它的任意子群为 $H$,对于任意 $g \in G$$h \in H$,有 $hg= gh$,因此 $H$ 为正规子群。证毕。

Abel群的交换律可以传递到子群,左右陪集相等,所以所有子群都是正规子群,可以构造商群。

6. Abel群的商群均是Abel群。

点我展开证明👀

设群 $(G, 🐔)$ 为Abel群,它的任意子群 $H$ 均是正规子群,可以构建商群 $G/H$。对于任意 $a, b \in G$$h \in H$,根据交换律,有 $(ah) (bh) = ahbh = bhah = (bh) (ah)$,因此有 $(aH)(bH) = (bH)(aH)$。因此,Abel群的商群均是Abel群。证毕。

Abel群的交换律可以传递到商群。

3. 总结

这一讲很轻松,我们介绍了具有交换律的Abel群及其性质。密码学和零知识证明中的常用群都是Abel群,之后我们还会经常见到它。