群论相关概念入门

周海汉 2018-06-25
2018-06-25

概述

简单理解,群是一种代数结构,由一个集合以及一个二元运算所组成。

\[集合+运算=群\]

一个群必须满足一些被称为“群公理”的条件,也就是封闭性、结合律、单位元和对于集合中所有元素存在逆元素。 群与对称概念共有基础根源。对称群把几何物体的如此描述物体的对称特征:它是保持物体不变的变换的集合。这种对称群,特别是连续李群,在很多学术学科中扮演重要角色。

区块链中使用到的椭圆曲线公私钥和签名理论,用到群论知识。本文算是基本群论入门。主要参考了知乎和维基。

密码学依赖于抽象群论方式和从计算群论中特别是实现于有限群上的时候所得到的算法知识的结合。

群定义

群是一个集合G,连同一个运算”·”,它结合任何两个元素a和b而形成另一个元素,记为a·b。符号”·”是对具体给出的运算,比如整数加法的一般占位符。要具备成为群的资格,这个集合和运算(G,·)必须满足叫做群公理的四个要求: $$

  1. 封闭性: 对于所有G中a, b,运算a·b的结果也在G中。
  2. 结合性: 对于所有G中的a, b和c,等式 (a·b)·c = a· (b·c)成立。
  3. 单位元: 存在G中的一个元素e,使得对于所有G中的元素a,等式 e·a = a·e = a 成立。

  4. 逆元: 对于每个G中的a,存在G中的一个元素b使得a·b = b·a = e,这里的e是单位元。 $$

进行群运算的次序是重要的。换句话说,把元素a与元素b结合,所得到的结果不一定与把元素b与元素a结合相同; 亦即,下列等式不一定恒成立:

${\displaystyle a\cdot b=b\cdot a}
$

这个等式在整数于加法下的群中总是成立,因为对于任何两个整数都有 a + b = b + a (加法的交换律)。但是在对称群的例子中不总是成立。

概念

阿贝尔群

使等式 a·b = b·a 总是成立的群叫做阿贝尔群(以尼尔斯·阿贝尔命名)。因此,整数加法群是阿贝尔群,而对称群不是。

群同态

X = { x, y, z }来表示集合X包含元素x、y和z,或 ${\displaystyle x\in X}$来表示x是X的一个元素。

记法

\[{\displaystyle f:X\to Y}\]

$f:X\to Y$意味着f是对X的所有元素指定Y的一个元素的函数

群同态是保持群结构的函数。两个群之间的函数 a: G → H 是同态,如果等式 a(g·k) = a(g)·a(k) 对于所有G中的元素g、k都成立。

群同构

复合函数:两个函数的复合函数指一个将第一个函数作用于参数,然后再将第二个函数作用于所得结果的函数。

恒等函数:恒等函数总数传回和输入值相同的函数值。即 f(x) = x。

两个群G和H被称为同构的,如果存在群同态 a: G → H 和 b: H → G ,使得复合函数先后(以两种可能的次序中每个次序)应用两个函数分别等于G和H的恒等函数。就是说,对于任何G中的g和H中h,有 a(b(h)) = h 和 b(a(g)) = g 。从抽象的观点来看,同构的群携带了相同的信息。

整数

整数Z在加法下的群记为(Z, +),它在上面已经描述了。整数带有用乘法替代加法的运算,(Z, ·)不形成群。闭合、结合律和单位元公理满足,但逆元不存在:例如, a = 2 是整数,但方程 a·b = 1 的唯一解在这种情况下是b = 1/2,它是有理数而非整数。因此不是所有Z的元素都有(乘法)逆元。

有理数

对乘法逆元存在的要求建议了考虑分式

${\displaystyle {\frac {a}{b}}}$

。 整数的分式(要求b非零)叫做有理数。所有这种分数的集合通常记为Q。对于有理数带有乘法(Q,·),成为群仍有一个小障碍:因为有理数0没有乘法逆元(就是说没有x使得 x·0 = 1 ),(Q, ·)仍然不是群。

但是,所有非零有理数的集合 Q{0} = {q ∈ Q, q ≠ 0} 形成一个在乘法下的阿贝尔群,记为(Q{0},·)。结合律和单位元公理从整数的性质中得出。闭合要求在去掉零之后仍成立,因为任何两个非零有理数的乘积永远不是零。最后,a/b的逆元是b/a,所以逆元公理也满足。

有理数(包括0)在加法下也形成群。同时带有加法和乘法运算产生更复杂的结构叫做—如果同时除法总是可能的话(如在Q中)就是,它在抽象代数中占据中心位置。群论理论因此位于这些实体的理论的底层部分。

非零整数模以素数

对于任何素数p,模算术提供了整数模以p的乘法群。群的元素是不能被p整除的整数模p的同余类,就是说两个数被认为是等价的如果它们的差被p整除。例如,如果 p = 5 ,则精确地有四个群元素1, 2, 3, 4:排除了5的倍数而6和−4都等价于1。群运算给出为乘法。因此 4·4 = 1 ,因为通常意义下的乘积16等价于1,而5整除 16 − 1 = 15 。以上事实记为

16 ≡ 1(mod 5)

p的首要作用是确保了两个都不被p整除的整数的乘积也不被p整除,因此指示的同余类的集合在乘法下闭合。单位元如平常的乘法群一样是1,而结合律可以从整数的相应性质得出。最后,逆元公理要求给定不整除于p的整数a,存在一个整数b使得

a · b ≡ 1(mod p),

就是说p整除a·b − 1的差。 逆元b可以使用裴蜀等式和最大公约数gcd(a, p)等于1的事实找到。在上述 p = 5 的情况下,4的逆元是4,3的逆元是2,因为 3·2 = 6 ≡ 1 (mod 5) 。所有的群公理都满足。实际上,这个例子类似于上述(Q{0},·),因为它是在有限域$F_p$中非零元素的乘法群,记为${F_p}^×$。这些群对于公开密钥加密是至关重要的。

循环群

循环群是其所有元素都是特定元素a的的群(在群运算被写为加法的时候使用术语倍数) 在乘法符号下,群的元素是:

\[...,a^{-3}, a^{-2},a^{-1}, a^0 = e, a, a^2, a^3,...\]

这里的$a^2$意味着a·a,而$a^{-3}$表示$a^{-1}·a^{-1}·a^{-1}=(a·a·a)^{-1}$等等。这个元素a叫做这个群的生成元或本原元。

群${F_p}^×$可以被证明为是循环群:对于 p = 5, 3是生成元因为 $3^1 = 3, 3^2 = 9 ≡ 4, 3^3 ≡ 2, 3^4 ≡ 1 $。 循环群是阿贝尔群。

有限群

一个群被称为有限群,如果它有有限个元素。元素的数目叫做群G的

一类重要的有限群是n次对称群$S_N$,它是N个字母的排列的群。例如,在3个字母上的n次对称群S3是由三个字母ABC的所有可能排列构成的群,就是说它包含元素ABC, ACB, …,直到CBA,总共有6(或3的阶乘)个元素。

举例

集合

$$

{心、肝、脾、肺、肾} $$

集合之间的组合运算

对象之间的相互作用,操作或运算,构成世界 $$

{ {心、肝、脾、肺、肾},{作用} }-> 人 $$

自然数$N$,通过各种运算得到其他集合$N,Z,Q,R,C$即整数,有理数,实数,复数。

\[N -{+-}> Z -{*/}-> Q -{柯西序列}> R -{R(i)}> Z\]

群的作用是描述对称。 对称指某种操作下的不变性

正方形,物理定律,多项式的根

群论发展

  1. 韦达定律:数学家发现根与方程系数的关系
  2. 通过系数计算根的时候发现对称性
  3. 伽罗瓦根据根的对称性发现了伽罗瓦群
  4. 群论蓬勃发展

符号化

类比加法

$$

旋转0度 -> 0 90 度-> r 180 度 -> 2r 270 度 -> 3r $$

保持不变+旋转90度(r)最终是旋转90度=0+r=r

旋转90度+旋转90度=180度=r+r=2r

类比乘法

旋转角度

\[0^o-> 1 90 -> r 180 -> r^2 270 -> r^3\]

这里的加法和乘法类似于模加法和模乘法,如钟表的12进制。

\[3+11=2 3\times6=6\]

我们得到两个群,一个是$({G,+})=({0,r,2r,3r},+)$ 群,一个$({G,\times})=({1,r,r^2,r^3},\times)$群。只是符号和运算不一样,可以称为同构。

参考

知乎 如何直观理解群论

wiki 群论


如非注明转载, 均为原创. 本站遵循知识共享CC协议,转载请注明来源