我的第一篇谈到具体学科的博客,还是献给我最钟爱的数学。

随记2018年3月31日


  个人比较喜欢离散数学,并非因为曲高和寡,而是因为数学分析、概率论、拓扑学、泛函之类的高手实在太多。而离散数学更为抽象,抽象到抽象代数直接以抽象二字命名,愿意去学习的人自然就少了,那么个人闲聊的时候忽悠的空间就会比较大,夸张夸张也没多少人看出自己其实是不学无术的。也正因为如此,喜欢离散数学,离散数学中最喜欢的就算是抽象代数了。

密码学中的离散数学知识学习

密码学中的近世代数实在是让人头疼,在实际阅读文章中很吃力,于是决心下点苦工补一补代数的知识.
(本科有学习过离散数学, 终于还是吃了数学的亏.
谁要是再说学数学没用我就*@$%!)

首先是学习这篇文章里的知识点,和之前学习过的离散数学无异,
但是这篇文章好就好在了深度展开了许多知识点, 并用较为简洁的例子讲解.
但是呢, 有点不足的是, 因为代数系统他是一环扣一环的,
有很强的迭代,往往会让人拎不清谁是谁.
本文引用这篇文章就想能更加拎清楚概念.

  数学是什么

  从人类原始社会起,人类与地斗,与天斗,物质资源极端匮乏,长期以往,人类对自己所控制的物质资源有了个量化的概念,再精确下去,就产生了计数。后来随着私有制的产生,加法、减法、乘法、除法也就慢慢产生了。农耕民族更容易更早产生面积的概念,从而产生几何学。Newton对于经典力学的奠基同时促进了数学的发展,尽管Newton所建立的微积分并未建立在无穷小分析基础之上,从而存在缺陷,这后来是Cauthy最终解决的,但无论如何,Newton是高等数学的祖师爷。之后源源不断的数学问题,解决过程中伴随着反复的抽象过程,从而不断建立新的数学学科,乃至完善。在数理逻辑完善前,人们认为数学是冥冥中注定的,它的底层是哲学保证的;然而在数理逻辑完善后,人们才意识到数学原来是自圆其说。

  再回到之前的这个问题,数学是什么,佛感觉一个无形的手在数学后面推着,数学是什么可能真的是一个见仁见智的问题。而我却总是意淫式的觉得数学是和我们物理的宇宙不一样的一个虚拟宇宙,是一切推理的抽象。

离散数学基础

  尺规作图

  尺规作图是古老的几何问题,它模拟了一个无限长的直尺以及一个可以任意半径的圆规,其规则如下:

  1.过任意两个不同的已知点可以作过两点的一条直线。

  2.任意两条直线,其交点为已知点。

  3.任意两个圆,其交点为已知点。

  4.以已知点为圆心,以任意两个已知点之间的距离为半径,作圆。

  5.作图只能在以上4条的有限步骤之内完成。

  初始的时候,至少要有两个已知点。

  从古希腊开始,人们就被三大尺规作图问题困扰:

  1.立方倍积:已知线段a,做图得到体积为2*a3的正方体的边长。

  2.画圆为方:已知道线段a,作图得到面积为π*a2的正方形的边长。

  3.三等分角:已知道角度a,作图得到角度a/3。

二次关系

一些其他的二次关系就暂且不提,只说一些与密码学相关的.

二次关系的一些性质:(其中,A是集合,R是集合中的关系)

自反性 反自反性 对称性 反对称性 传递性
定义 X∈A,有<x,x>∈R x∈A,有<x,x>不∈R 若<x,y>∈R,则<y,x>∈R 若<x,y>∈R,则<y,x>不∈R 若<x,y>∈R,且<y,z>∈R,则<x,z>∈R

等价关系和偏序关系

等价关系: R是非空集A的关系,如果R是 自反,对称,传递
的,则称R为A上的等价关系.
举个栗子: 在实数集合中, 等号’=’就是一个等价关系.假设a=b=c=1;
a,b,c都∈实数R;符合自反性:a=b;
符合对称性:a=b则b=a;符合传递性:a=b且b=c,则a=c;

偏序关系: R是非空集A的关系,如果R是 自反,反对称,传递
的,则称R为A上的偏序关系.
举个栗子: 在实数集合中, 大等于号’≥’就是一个偏序关系. 假设a≥b≥c;
a,b,c都∈实数R; 符合自反性: a≥a; 符合反对称性: a≥b 则 b不≥a;
符合传递性: a≥b且b≥c,则a≥c;
若集合S上定义了一个偏序R,则S成为 威尼斯人注册,偏序集 <S,R>
设有偏序集<S,≤>, (note:偏序关系’≤’并非实数的小等于)

  1. 若有任意x∈S,且b≤x,则称b为S的 下界 ;
  2. 若有任意x∈S,且x≤b,则称b为S的 上界 ;
  3. 若b是一个下界,且对于每一个S的下界b’都有b’≤b,则b是S的
    最大下界或下确界 .
  4. 若b是一个下界,且对于每一个S的下界b’都有b≤b’,则b是S的
    最小上界或上确界 .
    (Note: 上界和下界有可能不唯一)

  一元五次方程求解

  早在古希腊的时候,人们就知道一元二次方程如何根式求解。

  十六世纪之前,人们一直认为一元三次方程如同三大尺规作图一样,基本无法得到根式解的。十六世纪的时候,意大利数学家Ferro解出了形如x3+m*x+n=0这样的一元三次方程的根式解,Tartaglia彻底解决了一元三次方程的根式求解,直到Ferrari搞定一元四次方程根式求解问题。至此,一元三次方程、一元四次方程都有了根式求解,且都是被意大利数学家解决的。

  以后的连绵两三个世纪,人们在探索着一元五次方程的根式解,可是却一直没法解决。

  冥冥中注定了,此问题最终成就了数学史上的大事。

二元运算及其性质

代数中的二元运算的内容和小学学过的乘法结合律,交换了,幂等律差不多,所以不再详细说.
主要介绍幺元,零元,逆元的定义.(假设*是集合S中的二元运算)

  1. 幺元 : 若存在元素e∈S,使任何x∈S,有 e*x=x, x*e=x
    则,e是集合S中关于*运算的幺元. 就像1在实数集合关于×运算的幺元.
  2. 零元 : 若存在元素θ∈S,使任何x∈S,有 θ*x=θ, x*θ=θ
    则,θ是集合S中关于*运算的零元. 就像0在实数集合关于+运算的零元.
  3. 逆元 : e∈S是运算*的幺元, 对任意x∈S,若存在y∈S,且 y*x=e, x*y=e
    则,y是x的逆元.
    就像所有实数(除0之外)在实数集合中的倒数,相乘都等于关于×运算幺元1,这些相应的倒数就是这些实数的逆元.

  Galois

  现在轮到我们的主角出场了。

  Galois
1811年10月25日出生,父亲是一个市长,当时的法国处于革命的热潮之中,他的父亲也是一个革命的支持者。受其父亲的影响,Galois短暂的一生与法国革命有着重要的关系,作为一位革命者,有着革命志士的情怀与浪漫。

  Galois从小就表现出很高的天分,但自从学习了数学之后对其他的科目再无兴趣。最终又因为糟糕的表达能力,最终无法被其向往的综合工科大学录取。在他第二次报考该大学的时候,他父亲在选举中又被人恶意中伤而自杀,这对他打击很大,从而第二次报考依然无法被录取。名落孙山的他最终来到了一个师范大学。

  自从学习了数学之后,Galois想与前人一样,来攻占一元五次方程的数学堡垒。最终证明了其实一元n次方程(n≥5)是不存在通用的根式求解的。

我来换句话来说明Galois到底证明了什么,用程序员听的懂的语言。先建立这么5个复数上的函数:

  (1)    复数加法

  (2)    复数减法

  (3)    复数乘法

  (4)    复数除法

  (5)    正整数次根

  严格的说,正整数次根不能算一个函数,因为一个不为0的复数会有n个n次根。但这n个不同的根的辅角是不一样的。于是可以把这个根式补充一下,从而成为一个函数:

      先定义复数的辅角在区间[0,2π)中取。函数sqrt(c, n,
d),其中c是复数,n是正整数,d为小于等于n的正整数,代表复数c的n个n次根中辅角第d大的这个值。

     
于是5个函数都有了。Galois证明的是,存在整系数的一元五次方程没有一个根可以通过任意整数有限次使用以上5个函数构造出来。

     
再看看这个描述,是否觉得和之前的尺规作图看起来很像?是的,Galois也通过一样的模型证明了三大尺规作图问题是不可能完成的。

     
Galois把他的研究成果写成论文,投给法国科学院,审稿人是Cauthy,一说是Gauss,反正是这两大牛中的一个。结果据说还是由于Galois糟糕的表达能力,最终被这位审稿的大牛传为笑柄,连稿子都找不到了。Galois就这么被埋没了……

     
Galois作为革命者曾经两度入狱,第二次入狱的中认识了狱医的女儿。疯狂的人有着疯狂的爱情,疯狂的爱情催生疯狂的举动,终于,Galois和他的情敌——另外一个有着贵族身份的革命者,相约决斗。决斗前夕,可能因为Galois的情敌是位神枪手,他已经预见了自己的结局,连夜赶出61页的稿子,并交给了他的朋友,这是1832年5月28日夜。5月30日清晨时分,一位农民在巴黎的葛拉塞尔湖附近看到了重伤的他,送到医院。第二天,1832年5月31日早上,也就是185年前的今天,Galois不治身亡,死前,对他身边哭泣的弟弟说:“不要哭,我需要足够的勇气在20岁的年纪死去”。死后,尸体在公墓边随便葬了,至今难寻踪迹。

典型代数系统

   抽象代数

     
Gailos死后几十年,手稿到了一个三流数学家手中。这位数学家耐心的看完手稿,并细心研究他的成果,惊为天人。

     
Galois为群论奠基,并梳理了域论的一些东西,正是以此为工具,Galois解决了一元n次方程根式求解、三大作图问题,以及所有可以用尺规作图作出的正n边形的n满足的条件。牛的不是后面的结果,而是这个工具,那是一个让人激动的学科,有的人说,牛顿的微积分再晚些时候也会有人创造出来,而这种看待数学的思维却非得这种不世出的天才不可。相比来说,Gauss对于数学的贡献,光从境界上看,就比Galois低了一个级别,而Galois是从本质上去看待数学这种学科。那完全是从另外一个角度来看待数学这个东西,那是一个从所有数学中提纯出来的东西,研究对象为前所未有的一个叫代数系统的东西,从而我们学过的所有数学归根结底上都成了抽象代数的一个数学建模(其实即便是底层如数理逻辑者也是受了抽象代数的启发)。大师已经指明了探索的方向,于是在接着的百年时间里,人们陆续完善了群论、环论、域论、格论、模论这些抽象代数的分支。

     
一个月前,一同事研究加密解密的时候不理解Galois域(有限域的另一个名字,一般计算机里使用特征2域)的计算,来问我。他是一个打破沙锅问到底的家伙,我实在不忍心直接告诉他Galois域怎么计算加减乘除,当然即便我草草作答他也绝不会放过我。于是,我花了一个多小时从头到尾帮他了解了群、环、域,甚至于一些定理的证明,当然,他听的半懂半不懂倒也是真,不过倒是听的很有兴趣,那我也算是没白讲了。最后,一条vim
galois_field.c命令准备用C语言现写Galois域的计算方法,不过由于他编程能力也很强,于是还没开写就打住了。我告诉他,其实作为工程师最多只要知道Galois域怎么算的,而至于我之前说的那么一大通数学理论,不明白倒也关系不大,而加密之所以一般采用Galois域,其原因之一也就是有限的存储之内可以让加减乘除都封闭。

     
本文不打算解释Galois是怎么搞定这些问题的,这些在短短的章节恕我学艺不精实在没有那个水平写的通俗易懂,只是大致解释一下群论里相关的代数系统。

  n元运算:对于集合A上的一个n元运算,指的是A的n阶笛卡尔积An
->
A的一个映射。以我匮乏的数学知识,实在不知道人类目前有没有研究超过二元运算的代数系统的一般理论。

      二元运算:对于集合A上一个二元运算,指AXA –> A的一个映射。

     

半群

在一个集合S中定义了某种运算(记作加法“+”,但这个加法指代广泛意义上的运算,并不是指日常使用的加法),那么在这个集合上,如果这种运算满足以下性质,那么他和集合S共同组成一个半群,记作<S,+>:

封闭性。也就是运算的结果始终在集合S内

结合律。也就是满足:(a + b) + c= a + (b + c)

举例: 在实数集合R中,加法’+’符合封闭性:加法运算的所有结果都是实数;
符合结合律; 所以(R,+)形成半群.

半群:如果对于集合A上的一个二元运算,为了方便,用我们常用的数学符号来计,就叫a*b,如果对于A上的任何元素a、b、c,一定满足a*b*c

a*(b*c),也就是满足结合律,那么我们叫A在这个二元运算上构成一个半群。举个栗子,所有的偶数在数值乘法就合成一半群。其实,在群论里,我们一般都把这个运算叫乘法,当然此乘法非彼乘法。再举个极端的例子,对于所有实数,构造二元运算f(a,b),使得无论是什么实数a,b,f(a.b)都等于0,那么实数集在此f上也构成一个半群。

     
带e元的半群:假如一个半群中,存在一个特别的元素b,使得集合中任意的a,都有a*b
= e*b =
a,那么我们就把这个b叫作e元,把这个半群叫作带e元的半群。这里还是举个例子,所有整数在数值乘法上就构成这样的一个带e元的半群,1就是这个e元。

     
群:假如一个带e元的半群,对于集合中任何一个元素a,都可以找到集合中的一个b,使得a*b=b*a=e,那么我们就叫这个半群为群了,这里的a、b互为逆元。举个例子:所有非0实数在数值乘法上构成一个群,1是e元。注意,所有的实数在乘法上并无法构成一个群,因为0没有逆元。

     
交换群:又叫Abel群,也就是乘法满足交换律的群,也就是对于集合上任意a,b,满足a*b=b*a。What?乘法居然不满足交换律?淡定,难道忘了矩阵的乘法是不可交换的吗?要知道,实数的n阶非奇异方阵在矩阵乘法上也是构成一个群的。另外,交换群除了Abel群之外,还有一个名字,叫加法群。

     
子群:对于一个群,如果其子集在相同运算上依然合成一个群,那么这个新群叫这个群的子群。一个多于一个元素的群至少有两个子群,{e}和自身,这叫平凡子群。举个非平凡子群,实数集在加法上合成一个群,其子集有理数集在加法上也合成一群。

     
到现在为止,还没介绍过有限的群。其实Galois域在加法上就是一个有限群,但这个例子不够好,因为我不打算介绍环、域了。如下构造一个n阶加法群(也就是群里有n个元素),取集合{0,1,2…n-1},也就是从0开始的连续n个整数构成的集合,定义乘法a*b为a+b除以n的余数,0是这个群的e元,任意一个元素a的逆元是n-a除以n的余数(也就是0的逆元是0,其他不为0的元素a的逆元是n-a)。此群有个名字,叫n阶循环群。再举个咱码农更容易理解的有限群例子:{真,假}在异或运算上是一个群,”假”是该群的e元,这个群同构于2阶循环群。

     
群论就是研究群这样的代数系统的性质的学科,同理环论、域论、格论、模论。

     
今天是Galois的忌日,延续了几天的文字还是在今天发到网上。偶尔,我还是会拿出抽象代数翻看翻看,看看那些极度抽象的运算、代数系统,也算是一种对大师的敬意。正是Galois,让我们的数学不是拓展了广度,而是翻了维度。虽然Galois生前被埋没,死了之后其数学理论却可泽及万世,大师也能安息了。

幺半群

如果在一个半群<S,+>中存在一个幺元e,使得任意x∈S都有:

x + e = e + x = x

那么该半群就是一个幺半群.

举例: 在刚才例子中的半群<R,+>中,存在一个幺元0,使得任意x∈R都有 x +
0 = 0 + x = x.

如果在一个幺半群<S,+>中, 任意元素x∈S,都存在唯一对应元素y使得:

x + y = y + x = e , 其中e是幺元
即: 任意元素x∈S,都存在唯一逆元与之对应.

那么该幺半群就是一个 . 这样就在群中定义了减法.

交换群(Abel群)

如果一个群<S,+>符合交换律, 即对于集合S中任意元素x,y∈S,有:

x+y=y+x

那么这个群就是交换群.

来总结一下刚才所提到的群概念的迭代:

半群 幺半群 交换群
性质 封闭性,结合律 封闭性,结合律,存在幺元 封闭性,结合律,存在幺元,存在逆元 封闭性,结合律,存在幺元,存在逆元,交换律
迭代 +封闭性,结合律 +存在幺元 +存在逆元 +交换律

发表评论

电子邮件地址不会被公开。 必填项已用*标注