Abstract Algebra

Table of Contents

1 抽象代数简介

抽象代数(Abstract algebra)又称近世代数(Modern algebra),它作为数学的一门学科,主要研究对象是代数结构,比如群、环、域、格等。

19世纪30年代,在寻找五次方程求解方法的过程中,法国青年数学家伽罗瓦(E. Galois)提出了群的概念, 证明了五次以上的方程式没有公式解 。伽罗瓦彻底地解决了这个在长达200多年的时间使不少数学家伤透脑筋的问题。伽罗瓦是超越时代的天才,不仅仅是因为他在方程求解上的贡献,还因为他所发现的结果,他的奇特思想和巧妙方法,发展成为一门新学科——抽象代数学。伽罗瓦群论还给出了判断几何图形能否用直尺和圆规作图的一般判别法,圆满解决了三等分任意角或倍立方体的问题都是不可解的。一般称 伽罗瓦为抽象代数学的创始人。

本文主要参考:近世代数引论(第3版, 冯克勤等著)

1.1 什么是群、环、域

代数系统(又称代数结构)是抽象代数研究的主要对象。什么是代数系统呢? 代数系统是包含运算的集合。 典型的代数系统有群、环、域。简单地说,群(Group)是具有一个二元代数运算的代数系统;环(Ring)是具有两个代数运算的代数系统;域(Field)是满足一定条件的整环(Integral domain)。

2

2.1 集合基本知识

2.1.1 映射、满射、单射、双射

设 \(A\) 和 \(B\) 是两个非空集合,如果存在一个法则 \(f\) ,使得对 \(A\) 中的每个元素 \(a\) ,按法则 \(f\) ,在 \(B\) 中有唯一确定的元素 \(b\) 与之对应,则称 \(f\) 为从 \(A\) 到 \(B\) 的映射,记作: \(f:A \to B\) 或者 \(A \overset{f}{\longrightarrow} B\) 。而“ \(f\) 把 \(a\) 映射成 \(f(a)\) ”这件事可记为: \(a \mapsto f(a)\) 。
其中, \(b\) 称为元素 \(a\) 在映射 \(f\) 下的 , \(a\) 称为 \(b\) 关于映射 \(f\) 的 原象 。集合A中所有元素的象的集合称为映射 \(f\) 的 值域 ,记作 \(f(A)\) 。

如果 \(B\) 中每个元素均是 \(A\) 中某个元素在映射 \(f\) 下的象(即有 \(f(A)=B\) ),则 \(f\) 叫做满射(Surjection)。
如果 \(A\) 中不同的元素被 \(f\) 映射成 \(B\) 中的不同元素(即有 \(a,a' \in A, a \ne a' \Rightarrow f(a) \ne f(a')\) ),则 \(f\) 叫做单射(Injection)。
如果 \(f: A \to B\) 既是单射又是满射,则 \(f\) 叫做双射(Bijection),也可以称为一一映射或一一对应。

参考:https://zh.wikipedia.org/wiki/单射、双射与满射

2.1.2 置换(Permutation)

一个集合的置换(Permutation)是指该集合到自身的双射(Bijection)。

2.1.3 笛卡尔积(直积)

设 \(A\) 和 \(B\) 都是集合,我们把集合:
\[ A \times B = \{(a,b) \mid a \in A, b \in B \}\]
叫做 \(A\) 和 \(B\) 的 笛卡尔积(Cartesian product),又称为直积。

2.1.4 运算及其结合律、交换律

设 \(A\) 是集合,从 \(A \times A\) 到 \(A\) 的映射:
\[f: A \times A \to A\]
叫做 集合 \(A\) 上的一个(二元)运算 。我们经常把集合 \(A\) 上的运算表示为 \(\bullet\) ,即对于 \(a,b \in A\) , \(f(a,b)\) 写为 \(a \bullet b\) ,或者更简单地写为 \(ab\) 。

如果运算 \(\bullet\) 对任意 \(a,b,c \in A\) 都有:
\[a \bullet ( b \bullet c) = (a \bullet b) \bullet c\]
则称运算 \(\bullet\) 满足 结合律

如果运算 \(\bullet\) 对任意 \(a,b \in A\) 都有:
\[a \bullet b = b \bullet a\]
则称运算 \(\bullet\) 满足 交换律

2.2 群的正式定义

代数结构(algebraic structure,又称代数系统)是指装备了一个以上的运算的非空集合。 群是满足一定条件的代数结构。在介绍群之前,先介绍“半群”、“幺元素”、“逆元素”等概念。

半群定义:集合 \(S\) 和 \(S\) 上一个满足结合律的二元运算 \(\bullet\) 所形成的代数结构叫做半群(Semigroup)。
幺元素定义:设 \(S\) 是半群,元素 \(e \in S\) 叫做半群 \(S\) 的幺元素,如果满足对每个 \(x \in S, x \bullet e=e \bullet x=x\) 。 具有幺元素的半群叫做含幺半群(Monoid),或幺半群。
逆元素定义:设 \(S\) 是含幺半群(幺元素记为 \(e\) ),元素 \(y \in S\) 叫做元素 \(x \in S\) 的逆元素,如果满足 \(x \bullet y = y \bullet x = e\) 。 \(x\) 的逆元素可记为 \(x^{-1}\) 。
群定义:半群 \(G\) 如果有幺元素,并且每个元素均可逆,则 \(G\) 叫做群。

也可以像下面这样定义群。
一个集合 \(A\) 加上集合上一个二元运算 \(\bullet\) 的代数结构,可记为 \((A, \bullet)\) ,那么我们称 \(G=(A, \bullet)\) 为群(Group),当且仅当集合和运算满足以下几个条件:
(1) 封闭性(Closure): \(\forall a_1, a_2 \in A, \; a_1 \bullet a_2 \in A\)
(2) 结合律(Associativity): \(\forall a_1, a_2, a_3 \in A, \; (a_1 \bullet a_2) \bullet a_3 = a_1 \bullet ( a_2 \bullet a_3)\)
(3) 具有幺元素(Identity element,也称单位元): \(\exists e \in A, \; s.t. \; \forall a \in A, \; e \bullet a = a \bullet e = a\)
(4) 都有逆元素(Inverse element): \(\forall a \in A, \; \exists a^{-1} \in A, \; s.t. \; a \bullet a^{-1} = e\)

说明:如果仅满足(1)封闭性和(2)结合律,则 \(G\) 就是半群。

注:Haskell编程语言中实现了含幺半群(Monoid),参考:https://hackage.haskell.org/package/base-4.9.0.0/docs/Data-Monoid.html

2.2.1 交换群(阿贝尔群)

如果群中的二元运算 \(\bullet\) 还满足交换律,即:
(5) 交换律(Commutativity): \(\forall a_1, a_2, \; a_1 \bullet a_2 = a_2 \bullet a_1\)
则这个群又叫做交换群(Commutative Group),或阿贝尔群(Abelian Group)。

2.2.2 群的例子

设 \(M\) 为非负整数全体, \((M, +)\) 是含幺半群,幺元素为数0。但它不是群,因为 \(M\) 中除数0外,其它元素没有逆元素,不满足群的定义。
\(\mathbb{Z}, \mathbb{Q}, \mathbb{R}, \mathbb{C}\) 对于加法均是阿贝尔群,分别叫做“整数加法群”,“有理数加法群”,“实数加法群”,“复数加法群”。

2.2.3 群的阶(集合中元素的个数)

设 \((G, \bullet)\) 为群。若集合 \(G\) 中元素个数有限,则称 \((G, \bullet)\) 为“有限群”,否则叫“无限群”。

若有限群 \((G, \bullet)\) 中有 \(n\) 个元素,则称为 \(n\) 阶群, \(n= |G|\) 叫做有限群 \(G\) 的阶。

2.2.4 Additive group of integer modulo \(n\) (记为 \(\mathbb{Z}_n\) or \(\mathbb{Z}/n\mathbb{Z}\))


设集合 \(N = \{0, 1, 2, \cdots, n-1 \}\) ,定义 \(N\) 上的运算 \(+_n\) 如下:
\[\forall x,y \in N, \qquad x +_n y = x + y \pmod n \qquad \text{注:即为x+y除以n的余数}\]
容易验证 \((N, +_n)\) 是群:因为它满足封闭性,结合律,且具有幺元素(幺元素为0),每个元素都有逆元素(0的逆元为0,其它元素 \(x, x\neq0\) 的逆元为 \(n-x\) )。

注:上面介绍的群 \((N, +_n)\) 称为 Additive group of integer modulo \(n\) ,往往记为 \(\mathbb{Z}_n\) 或者 \(\mathbb{Z}/n\mathbb{Z}\) 。

2.2.5 Multiplicative group of integers modulo \(n\) (记为 \((\mathbb{Z}_n)^{\star}\) or \((\mathbb{Z}/n\mathbb{Z})^{\star}\))


设集合 \(N\) 是由集合 \(\{0, 1, 2, \cdots, n-1 \}\) 中和 \(n\) 互质(最大公因数为1)的数组成的 ,定义 \(N\) 上的运算 \(\times_n\) 如下:
\[\forall x,y \in N, \qquad x \times_n y = x y \pmod n \qquad \text{注:即为x乘y除以n的余数}\]
下面我们将证明 \((N, \times_n)\) 是一个群。考察群定义的4个要求,容易验证它满足封闭性,结合律,且具有幺元素(幺元素为1),难点在于如何判断它的每个元素是否都有逆元素。即对于任意 \(a \in N\) ,是否存在 \(x \in N\) 满足: \(a x = 1 \pmod n\) 呢?这个问题等价于 \(ax + ny = 1\) 是否有解,答案是肯定的。这是因为 \(gcd(a, n) = 1\) ,从而由裴蜀定理(又称贝祖定理, Bézout's identity) 知一定存在整数 \(x,y\) 满足: \(ax + ny = 1\) 。

注1:贝祖定理是指“两数的最大公约数可以用两数的整数倍相加来表示”,如:12和42的最大公因数是6,则方程 \(12x + 42y = 6\) 有解。事实上有 \(12 \times (-3) + 42 \times 1 = 6\) 及 \(12 \times 4 + 42 \times (-1) = 6\) 。特别地,方程 \(ax + by = 1\) 有解当且仅当整数 \(a\) 和 \(b\) 互质。
注2:贝祖定理描述的只是“存在逆元素”,具体如何求解逆元素可参考“扩展欧几里得算法(Extended Euclidean algorithm)”。
注3:上面介绍的群 \((N, \times_n)\) 称为 Multiplicative group of integers modulo \(n\) ,往往记为 \((\mathbb{Z}_n)^{\times}\) 或者 \((\mathbb{Z}/n\mathbb{Z})^{\times}\) 或者 \((\mathbb{Z}_n)^{\star}\) 或者 \((\mathbb{Z}/n\mathbb{Z})^{\star}\) 。

1 是 \((\mathbb{Z}_n)^{\star}\) 的一些例子。

Table 1: \((\mathbb{Z}_n)^{\star}\) 的一些例子
\((\mathbb{Z}_n)^{\star}\) Elements
\((\mathbb{Z}_5)^{\star}\) 1, 2, 3, 4
\((\mathbb{Z}_6)^{\star}\) 1, 5
\((\mathbb{Z}_7)^{\star}\) 1, 2, 3, 4, 5, 6
\((\mathbb{Z}_8)^{\star}\) 1, 3, 5, 7
\((\mathbb{Z}_9)^{\star}\) 1, 2, 4, 5, 7, 8
\((\mathbb{Z}_{10})^{\star}\) 1, 3, 7, 9
\((\mathbb{Z}_{11})^{\star}\) 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
\((\mathbb{Z}_{12})^{\star}\) 1, 5, 7, 11
\((\mathbb{Z}_{13})^{\star}\) 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12

参考:
https://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n

2.2.6 群元素的阶(“与单位元的距离”)


如果我们说在群里,单位元 \(e\) (即幺元)由于它的惟一性显得有些特别的话,那么其他的元素也有一些特殊的性质,其中之一就是与单位元的“距离”。

设 \((G, \bullet)\) 是群。且 \(a \in G\) ,则满足:
\[\underbrace{a \bullet a \bullet \cdots a}_{\text{$i$ 个 $a$ 重复群运算}} = e\]
的最小正整数 \(i\) 称为 元素 \(a\) 的阶,记为 \(ord(a)\) 。 如果这样的整数 \(i\) 不存在,则称元素 \(a\) 是无限阶元。

例:求群 \(\mathbb{Z}_{12}\) 中各个元素的阶。
解:因为 \(0 \equiv 0 \pmod {12}\) ,所以 \(ord(0) = 1\) ;
因为 \(\underbrace{1 + 1 + \cdots 1}_{12} = 12 \equiv 0 \pmod {12}\) ,所以 \(ord(1) = 12\) ;
因为 \(\underbrace{2 + 2 + \cdots 2}_{6} = 12 \equiv 0 \pmod {12}\) ,所以 \(ord(2) = 6\) ;
因为 \(3 + 3 + 3 + 3 = 12 \equiv 0 \pmod {12}\) ,所以 \(ord(3) = 4\) ;
因为 \(4 + 4 + 4 = 12 \equiv 0 \pmod {12}\) ,所以 \(ord(4) = 3\) ;
因为 \(\underbrace{5 + 5 + \cdots 5}_{12} = 60 \equiv 0 \pmod {12}\) ,所以 \(ord(5) = 12\) ;
因为 \(6 + 6 = 12 \equiv 0 \pmod {12}\) ,所以 \(ord(6) = 2\) ;
因为 \(\underbrace{7 + 7 + \cdots 7}_{12} = 84 \equiv 0 \pmod {12}\) ,所以 \(ord(7) = 12\) ;
因为 \(8 + 8 + 8 = 24 \equiv 0 \pmod {12}\) ,所以 \(ord(8) = 3\) ;
因为 \(9 + 9 + 9 + 9 = 36 \equiv 0 \pmod {12}\) ,所以 \(ord(9) = 4\) ;
因为 \(\underbrace{10 + 10 + \cdots 10}_{6} = 60 \equiv 0 \pmod {12}\) ,所以 \(ord(10) = 6\) ;
因为 \(\underbrace{11 + 11 + \cdots 11}_{12} = 132 \equiv 0 \pmod {12}\) ,所以 \(ord(11) = 12\) ;

2.2.6.1 群的阶和群元素的阶之间的关系


设 \(G\) 是一个有限群, \(a \in G\) 为任意元素,则群的阶 \(|G|\) 可以被 \(ord(a)\) 整除。这里不证明这个结论。

2.3 子群

设 \((G, \bullet)\) 为群, \(A\) 为 \(G\) 的子集。如果 \((A, \bullet)\) 也是群,则称 \(A\) 为 \(G\) 的子群(Subgroup),表示成 \(A \le G\) 。此外,若 \(A \ne G\) ,则称 \(A\) 为 \(G\) 的真子群(Proper Subgroup),表示成 \(A < G\) 。

任何群 \(G\) 都有两个子群(“仅包含幺元素的群”和“群 \(G\) 本身”),我们称这两个子群为平凡子群(Trivial Subgroup)。

2.3.1 子群的例子

例子1:对每个非负整数 \(n\) , \(n\mathbb{Z} = \{na \mid a \in \mathbb{Z} \}\) 是整数加法群的子群。

例子2:求群 \(\mathbb{Z}_4\) (其定义参见节 2.2.4 )的子群。
解:集合 \(\{0,1,2,3\}\) 的所有的非空子集如下:
\[\{0\},\{1\},\{2\},\{3\},\{0,1\},\{0,2\},\{0,3\},\{1,2\},\{1,3\},\{2,3\},\{0,1,2\},\{0,1,3\},\{0,2,3\},\{1,2,3\},\{0,1,2,3\}\]
此时仅有三个子集:
\[\{0\},\{0,2\},\{0,1,2,3\}\]

关于运算 \(+_4\) 满足群定义的4个要求。
(1)封闭性:运算 \(+_4\) 关于集合 \(\{0\}, \{0,2\}, \{0,1,2,3\}\) 是封闭的;
(2)结合律:这是显然的;
(3)幺元素存在:对集合 \(\{0\}, \{0,2\}, \{0,1,2,3\}\) 都有幺元素“0”存在;
(4)每个元素的逆元素存在:
对集合 \(\{0\}\) ,有: \(0^{-1} = 0\) ;
对集合 \(\{0,2\}\) ,有: \(0^{-1} = 0, 2^{-1} = 2\)
对集合 \(\{0,1,2,3\}\) ,有: \(0^{-1} = 0, 1^{-1} = 3, 2^{-1} = 2, 3^{-1} = 1\)

从而知: \((\{0\}, +_4), (\{0,2\},+_4), (\{0,1,2,3\},+_4)\) 是 \(\mathbb{Z}_4\) 的子群,其中子群 \((\{0\}, +_4), (\{0,1,2,3\},+_4)\) 为 \(\mathbb{Z}_4\) 的平凡子群。

例子3:和上一个例子类似。可知群 \(\mathbb{Z}_{12}\) 的子群有: \((\{0\}, +_{12})\), \((\{0,6\},+_{12})\), \((\{0,4,8\},+_{12})\), \((\{0,3,6,9\},+_{12})\), \((\{0,2,4,6,8,10\},+_{12})\), \((\{0,1,2,3,\cdots,10,11\},+_{12})\)

2.3.2 拉格朗日定理

拉格朗日定理:设 \(G\) 为有限群, \(A \le G\) (即 \(A\) 是 \(G\) 的子群),则 \(|A|\) 是 \(|G|\) 的因数。

拉格朗日定理的证明需要引入陪集(Coset)的概念,这里不证明。

拉格朗日定理是群论中简单而有用的定理。例如:一个6阶群只能有1,2,3,6阶子群,不能有4阶或5阶子群。

2.4 循环群

设 \(G\) 是乘法群(即带有乘法运算),若存在一个元素 \(g \in G\) ,使得任意元素 \(a \in G\) 都可以写为 \(a = g^i\) (其中 \(i \in \mathbb{Z}\) )的形式(即 任意元素 \(a\) 可由 \(g\) 重复多次群运算而得到 ),则称 \(G\) 为循环群(Cyclic Group),记为 \(G = \langle g \rangle\) ,并称 \(g\) 为该循环群的一个生成元(Generating Element)。 \(G\) 的所有生成元的集合称为 \(G\) 的生成集(Generating Set)。类似地,在加法运算的情况下,循环群定义成 \(\langle g \rangle = \{ ig\}\) (其中 \(i \in \mathbb{Z}\) )。

循环群最简单的例子是整数加法群,它由元素1或-1生成。

2.4.1 循环群性质

由循环群可以推导出很多有用的结论,如(证明略):
1、循环群的每一个子群均为循环群。
2、 \(G\) 为循环群,则对于 \(|G|\) 的每一个正因子 \(d\) , \(G\) 恰好包含一个 \(d\) 阶子群。
3、 \(G\) 为循环群,则对于 \(|G|\) 的每一个正因子 \(d\) , \(G\) 包含 \(\varphi(d)\) 个 \(d\) 阶元(注:这里 \(\varphi(n)\) 表示 Euler's totient function,即小于 \(n\) 且与 \(n\) 互素的正整数的个数)。

例: \(\mathbb{Z}_{12}\) (参见 2.2.4 )是循环群,因为任意元素都可以由元素1重复多次群运算 \(+_{12}\) 而得到。 \(|G|=12\) ,它的正因子有:1,2,3,4,6,12。从而,由上面的结论2有:
\(\mathbb{Z}_{12}\) 包含一个1阶子群(为 \(\{ 0 \}\) );
\(\mathbb{Z}_{12}\) 包含一个2阶子群(为 \(\{ 0,6 \}\) );
\(\mathbb{Z}_{12}\) 包含一个3阶子群(为 \(\{ 0,4,8 \}\) );
\(\mathbb{Z}_{12}\) 包含一个4阶子群(为 \(\{ 0,3,6,9 \}\) );
\(\mathbb{Z}_{12}\) 包含一个6阶子群(为 \(\{ 0,2,4,6,8,10 \}\) );
\(\mathbb{Z}_{12}\) 包含一个12阶子群(为 \(\{ 0,1,2,3,4,5,6,7,8,9,10,11 \}\) )。
由上面的结论3有(节 2.2.6 中介绍了 \(\mathbb{Z}_{12}\) 中各个元素的阶,可以去那里验证一下):
\(\mathbb{Z}_{12}\) 包含1阶元 \(\varphi(1)=1\) 个(为0);
\(\mathbb{Z}_{12}\) 包含2阶元 \(\varphi(2)=1\) 个(为6);
\(\mathbb{Z}_{12}\) 包含3阶元 \(\varphi(3)=2\) 个(为4和8);
\(\mathbb{Z}_{12}\) 包含4阶元 \(\varphi(4)=2\) 个(为3和9);
\(\mathbb{Z}_{12}\) 包含6阶元 \(\varphi(6)=2\) 个(为2和10);
\(\mathbb{Z}_{12}\) 包含12阶元 \(\varphi(12)=4\) 个(为1、5、7和11)。

2.4.1.1 素阶群都是循环群

如果群 \(G\) 的阶为素数(往往记为 \(p\) ),则群 \(G\) 一定是循环群,而且群 \(G\) 中任意非单位元均为生成元。
证明:设 \(a \in G\) 为任意非单位元,由 2.2.6.1 节中的结论有: \(ord(a)\) 可以被 \(|G|=p\) 整除,而 \(p\) 是素数,从而 \(ord(a) = 1\) 或者 \(ord(a) = p\) 。又由于 \(a\) 不是单位元,所以 \(ord(a) \neq 1\) ,从而 \(ord(a) = p\) 。所以它生成的 \(G\) 的循环子群的阶也是 \(p\) ,从而等于整个群 \(G\) ,所以 \(G\) 等于它的任一非单位元生成的循环群。证毕。

2.4.2 循环子群

设 \(G\) 为群,则 \(G\) 中每个元素 \(a\) 生成的循环群 \(\langle a \rangle\) ,都称为 \(G\) 的循环子群(Cyclic Subgroup)。

2.5 正交群O(n),特殊正交群SO(n)

实数域上所有 \(n\) 维正交矩阵组成的集合,对于矩阵的乘法可构成一个群,称为正交群(Orthogonal Group),记作 \(O(n)\) 。特别地,对应行列式为1或者-1的所有 \(n\) 维正交矩阵组成的集合,对于矩阵乘法也可构成一个群,称它为特殊正交群(Special Orthogonal Group),记作 \(SO(n)\) 。特殊正交群又称为旋转群(Rotation Group),因为在2维(记为 \(SO(2)\) )或3维(记为 \(SO(3)\) )情况下,它的元素可以用来表示物体的旋转。

参考:
https://en.wikipedia.org/wiki/Orthogonal_group
https://en.wikipedia.org/wiki/Rotation_group_SO(3)

2.5.1 特殊欧氏群SE(n)

我们可以把 刚体的“平移”和“旋转”两种运动记在一个矩阵中 ,这个 \((n+1) \times (n+1)\) 矩阵有下面形式:
\[\left\{ \begin{pmatrix} R & v \\ 0 & 1 \\ \end{pmatrix} \bigg| R \in SO(n) \; \text{and} \; v \in \mathbb{R}^n \right\}\]
上面矩阵组成的集合对于矩阵乘法构成的群称为特殊欧氏群(Special Euclidean group),记为 \(SE(n)\) 。

参考:
https://en.wikipedia.org/wiki/Euclidean_group
http://planning.cs.uiuc.edu/node147.html

3

环(Ring)是一个集合 \(R\) 和 \(R\) 上两个二元运算(通常表示成加法 \(+\) 和乘法 \(\bullet\) )组成的代数结构 \((R, +, \bullet)\) ,并且满足以下三个条件:
(1) \((R, +)\) 是阿贝尔群。
(2) \((R, \bullet)\) 是半群。这意味着 \(R\) 中乘法运算满足结合律。
(3) 加法和乘法满足分配律。即对任意的 \(a,b,c \in R\) ,有: \(a \bullet (b + c) = a \bullet b + a \bullet c, \; (b + c) \bullet a = b \bullet a + c \bullet a\).

注记:如果只是前两个条件,那么 \(R\) 不过是具有阿贝尔群 \((R, +)\) 和乘法半群 \((R, \bullet)\) 两个彼此孤立的代数结构。正是条件(3)将两个运算用分配律联系在一起,从而形成新的代数结构——环。

如果环 \(R\) 还满足条件:
(4) 对所有 \(a,b \in R\) 有 \(a \bullet b=b \bullet a\) 。
则称 \(R\) 为“交换环”。这里“交换”二字是表明 \(R\) 中乘法满足交换律(因为环中加法永远规定有交换律)。

3.1 特征(Characteristic)


设 \(R\) 为环,如果存在正整数 \(m\) ,使得对每个 \(r \in R\) 均有 \(\underbrace{r + r + \cdots + r}_{\text{m times}} = 0\) ,我们把满足此条件的最小正整数 \(m\) 称为环 \(R\) 的特征。如果不存在这样的正整数 \(m\) ,便称环 \(R\) 的特征是零。

4

域(Field)是一个集合 \(F\) 和 \(F\) 上两个二元运算(通常表示成加法 \(+\) 和乘法 \(\bullet\) )组成的代数结构 \((F, +, \bullet)\) ,并且满足以下几个条件(没特别说明时假设 \(a,b,c\) 是 \(F\) 中任意元素):
(1) 加法和乘法具有结合性。即 \(a + (b+c)=(a+b)+c, \; a\bullet(b \bullet c) = (a \bullet b) \bullet c\)
(2) 加法和乘法满足交换律。即 \(a + b=b+a, \; a\bullet b = b \bullet a\)
(3) 加法和乘法都有幺元素,并且这两个运算下的幺元素不相同,分别记为0和1。即 \(a + 0 = a, \; a \bullet 1 = a\)
(4) 所有元素的加法运算具有逆元素, \(a\) 的加法逆元素记为 \(-a\) 。即 \(a + (-a) = 0\)
(5) 除加法幺元素0外的所有元素的乘法运算具有逆元素, \(a\) 的乘法逆元素记为 \(a^{-1}\) 或者 \(\frac{1}{a}\) 。即 \(a \bullet a^{-1} = 1, a \neq 0\)
(6) 加法和乘法满足分配律。即 \(a \bullet (b + c) = a \bullet b + a \bullet c, \; (b + c) \bullet a = b \bullet a + c \bullet a\)

注:域还有其它等价的定义形式,如在集合上定义加减乘除4种运算。显然,域是特殊的环。

有限群、子群、群的阶等概念可以直接推广到环和域。

在通常的加法和乘法运算下, \(\mathbb{Q}, \mathbb{R}, \mathbb{C}\) 都是域。注意, \(\mathbb{Z}\) 不是域,比如2对于乘法运算没有逆元素(因为 \(\frac{1}{2}\) 并不在 \(\mathbb{Z}\) 中)。

4.1 有限域

如果域中元素个数有限,则称为有限域(Finite field,也称为Galois Field)。阶(即元素的个数)为 \(n\) 的有限域一般记为 \(\text{GF}(n)\) ,GF是Galois Field的缩写。

1 是有限域的例子,它含有4个元素。如果只包含两个元素 \(O,I\) ,即红色部分 \((\{O, I\}, +, \bullet)\) 也是域,它是最小的域。

abstract_algebra_field.png

Figure 1: 具有4个元素的域

定理: 有限域的阶(即元素的个数)一定是一个素数的幂(即可表示为 \(p^n\) 的形式,其中, \(p\) 为素数, \(n\) 为正整数)。 且 \(p\) 就是有限域的“特征”(即对每个元素 \(a\) 均有 \(\underbrace{a + a + \cdots + a}_{p \text{ times}} = 0\) ,特征的定义参考节 3.1 )。

4.2 有限素域 \(\text{GF}(p)\)

前面介绍过有限域的阶一定是一个素数的幂(可表示为 \(p^n\) 的形式),这一节介绍当 \(n=1\) 时的特殊情况。

采用下面的定义可以构造出一个素域 \(\text{GF}(p)\) :
1、集合为 \(\{0, 1, 2, \cdots, p - 1 \}\) ,其中 \(p\) 为素数;
2、加法运算为“模 \(p\) 加法”运算 \(+_p\) (这个记号可参考节 2.2.4 );
3、乘法运算为“模 \(p\) 乘法”运算 \(\times_p\) (这个记号可参考节 2.2.5 );
4、加法幺元素为0,乘法幺元素为1;
5、任意元素 \(a\) 的加法逆元素由 \(a + (-a) = 0 \pmod p\) 给出(注:可求出加法逆元 \(-a\) 为 \(p-a\) );
6、任意非零元素 \(a\) 的乘法逆元素由 \(a \times a^{-1} = 1 \pmod p\) 给出(注:可由“扩展欧几里得算法”求出乘法逆元 \(a^{-1}\) )。
基于上面定义,容易验证它满足域的所有条件。

4.2.1 实例: \(\text{GF}(7)\)

2 (摘自Cryptography and Network Security - Principles and Practice, 6th Edition)演示了 \(\text{GF}(7)\) 的两种运算及在这两种运算下的逆元素。

abstract_algebra_gfp.png

Figure 2: \(\text{GF}(7)\)

4.3 有限域 \(\text{GF}(2^n)\)

前面介绍过有限域的阶一定是一个素数的幂(可表示为 \(p^n\) 的形式),这一节介绍当 \(p=2\) 时的特殊情况。

我们可以采用前一节构造素域 \(\text{GF}(p)\) 的思路来构造 \(\text{GF}(2^n)\) 吗?即定义集合元素为小于 \(2^n\) 的非负整数,定义加法运算为“模 \(2^n\) 加法”运算,定义乘法运算为“模 \(2^n\) 乘法”运算。答案是当 \(n>1\) 时(当 \(n=1\) 时,显然就是上一节的特殊情况),不能!因为这样的定义不能满足域的所有条件。

为了构造有限域 \(\text{GF}(2^n)\) ,我们将:
1、使用不同的符号表示域内的元素(后面会介绍,其元素是多项式);
2、使用不同的规则定义域的加法运算和乘法运算。

构造 \(\text{GF}(2^n)\) 会涉及“多项式运算”。这里不详细介绍,仅给出 \(\text{GF}(2^3)\) 的一个例子。

为了构造 \(\text{GF}(2^3)\) ,我们需要选择一个3次既约多项式(Irreducible Polynomial)。只有两个满足条件的多项式: \(x^3 + x^2 + 1\) 和 \(x^3 + x + 1\) 。这里我们仅考虑选择 \(x^3 + x + 1\) 为既约多项式时如何构造 \(\text{GF}(2^3)\) ,具体构造如图 3 所示。在这个 \(\text{GF}(2^3)\) 中,域元素集合是多项式集合 \(\{0, 1, x, x+1, x^2, x^2 + 1, x^2 + x, x^2 + x + 1 \}\) (也可以表示为 \(\{000, 001, 010, 011, 100, 101, 110, 111 \}\) ),加法运算是模 \(x^3 + x + 1\) 的多项式加法,乘法运算是模 \(x^3 + x + 1\) 的多项式乘法。

abstract_algebra_gf8.png

Figure 3: \(\text{GF}(2^3)\) 实例:以 \(x^3 + x + 1\) 为模的多项式运算

参考:Cryptography and Network Security, 6th Edition, Chapter 4 Basic Concepts in Number Theory and Finite Fields


Author: cig01

Created: <2016-06-09 Thu 00:00>

Last updated: <2018-05-27 Sun 23:50>

Creator: Emacs 25.3.1 (Org mode 9.1.4)