2022-06-06 21:01 已编辑门头沟学院芯片研发

关注

密码学数学基础之群论基础

本节课介绍代数学中的群论。

群是抽象代数研究的主要数学对象之一，是一种最基础的代数结构。
群的概念从19世纪初开始出现，是数学家在研究五次及五次以上代数方程根式解的过程中出现的一个新概念，到20世纪初群的理论逐渐趋于完备，成为整个现代代数学的基石。

群的定义

定义1：给定非空集合G和G的一个运算“◦”，称G及其运算构成一个群，如果满足以下4条公理：

（1）封闭性，对于集合G的任意两个元素a和b，还在G中。

（2）集合G的运算满足结合律，即对于集合G的任意三个元素a、b和c，(a◦b)◦c=a◦(b◦c)。
（3）集合G中存在一个特殊的元素，称为单位元，记作e，满足条件对于G中任意元素a，e◦a=a◦e=a。
（4）集合G中的任意元素a都存在逆元，记作 $a^{-1}$ ，满足条件： $a^{-1}$ ◦a=a◦ $a^{-1}$ =e。
定义2：一个群G称为Abel群（阿贝尔群），如果它满足条件：对于G中的任意元素a和b，ab等于ba。

也就是说，阿贝尔群中的元素乘法是满***换律的，因此阿贝尔群也称为交换群或者可换群。

在一般的群里面，运算往往习惯于被称为乘法，而在阿贝尔群中：

运算有时候被称为加法，
群称作加群
单位元称为零元，记作0
a的逆元称为负元，记作-a。

群的例子

例1 一些常见的由数的集合，如整数Z、有理数Q、实数R、复数C对于数的加法都构成了群。
例2 所有非零有理数记作Q*，可以证明Q*对于数的乘法构成一个交换群。
例3 实数R上的n阶可逆方阵全体（记作 $M_{n-inv}(R)$ ），对于矩阵的乘法构成一个群。

定义3：群G的元素个数称为G的阶，记作 $|G|$ 。若群G的阶有限，称G为有限群，否则称为无限群。

对于有限群G来说，存在正整数n，使得 $|G|=n$ ，对于无限群则不存在这样的正整数，因此一般记作 $|G|=\infty$ 。

例4 复数域内的n次单位根全体在复数乘法下构成一个群。

n次单位原根： $\varepsilon = e^{\frac{2\pi i}{n}}=cos\frac{2\pi}{n}+isin\frac{2\pi}{n}$

n次单位根全体： $U_{n}=\{\varepsilon,\varepsilon^{2},...,\varepsilon^{n-1},\varepsilon^{n}=1\}$

可以证明： $(U_{n},\cdot)$ 是一个交换群，且其阶为n。

例5 整数模n剩余类可以构成一个群

上一讲定义了整数模n剩余类 $Z_{n}$ ，现在我们为 $Z_{n}$ ，引入加法“ $\oplus$ ”运算，如下：

$\bar{s} \oplus \bar{t} = \bar{(s+t)modn}$

可以很容易验证 $Z_{n}$ 在这样的加法下构成一个交换群。

群元素的阶

符号说明：

$a^{0}=e$

$a^{n}=aa...a(n个a)$

$a^{-n}=(a^{-1})^{n}=a^{-1}a^{-1}...a^{-1}(n个a^{-1})$

定义4给定群G和G中任意元素a，若存在n使 $a^{n}=e$ ，则称满足此条件的最小正整数为a的阶，记作 $|a|=n$ ，若不存在这样的n，则称a的阶为无限，记作 $|a|=\infty$ 。

例6 有限阶元素的例子

我们取例4中的乘法群，令n=4， $U_{4}=\{1,-1,i,-i\}$ ，其中四个元素的阶均为有限。容易验证它们的阶分别为1,2,4,4。比如对于来说， $i^{1}=i$ ， $i^{2}=-1$ ， $i^{3}=-i$ ， $i^{4}=1$ 。

例7 无限阶元素的例子

正有理数乘法群 $(Q^{+}, \cdot)$ 中，除1之外的所有数的阶都是无限，因为所有不等于1的正有理数的任意正整数次幂都不会等于1。

定理1 有限群G中的任一元素a的阶一定有限。

证明：如果G包含n个元素，只需要考查元素a的n+1个正整数幂： $a,a^{2},a^{3},...,a^{n+1}$

用抽屉原理就可以得到这些正整数幂中必然有相等的，比如说 $a^{s}=a^{t}$ 那么这时候 $a^{s-t}=e$ ，因此a的阶有限。

定理2 如果群G中的元素a的阶为n，则 $a^{m}=e\Leftrightarrow n|m$ 。

充分性：如果设 $m=kn$ ，则 $a^{m}=a^{kn}=(a^{n})^{k}=e$ 。

必要性需要用带余除法：设 $m=kn+r,0\leq r\leq n$ ，于是 $e=a^{m}=a^{kn+r}=a^{kn}\cdot a^{r}=a^{r}$ 。

根据阶的定义，此时只能有 $r=0$ ，因此 $m=kn,n|m$ 。

定理3 如果群G中的元素a的阶为n，则 $|a^{k}|=\frac{n}{(k,n)}$ 。

证明设a的k次方的阶为s，则有 $(a^{k})^{s}=a^{ks}=e$ 。因为a的阶为n，所以一定有 $n|ks$ ，那么 $\frac{n}{(k,n)}|\frac{ks}{(k,n)}$ 。

根据最大公因子的性质： $(\frac{n}{(k,n)},\frac{k}{(k,n)})=1$ ，

所以可以进一步得到： $\frac{n}{(k,n)}|s$ ,

然后可以计算得到 $(a^{k})^{\frac{n}{(k,n)}}=(a^{n})^{\frac{k}{(k,n)}}=e^{\frac{k}{(k,n)}}=e$ ，

所以 $s|\frac{n}{(k,n)}$ 。

两个结果结合起来，就得到 $s=\frac{n}{(k,n)}$ 。

例8 在 $U_{6}=\{\varepsilon,\varepsilon^{2},\varepsilon^{3},\varepsilon^{4},\varepsilon^{5},\varepsilon^{6}=1\}$ ， $\varepsilon^{4}$ 次的阶为 $6/(4,6)=3$ ，可验证：