Lattices
Theory格伦(代数学的领域,其与我们海南琼州大学的导师钟集教授的关系就如文章《代数王钟集与黄际遇》,并钟先生担任中国最国际性成果评委会主席的委员陈杰教授的下面《格论初步》是中国第一本格论专著,海南琼州大学也给出格论一个重要定理的等价证明,和海南琼大合作多篇论文并评价琼大是世界领先水平的美国Lai院长根据他1991年在该校开设的拟阵论课程整理而成的《拟阵论》的第五章等也讲格论):
而关于我的导师的委员兼该省政协主席陈杰教授在我读研的1990年出版的中国第一本格论书,正如“序言”所说“本书是作者从1982年起,在为研究生开设格论课编写讲义的基础上修订而成的”“鉴于在我国至今还没有一本国人写的格论的著作,也由于中山正的书已远不能反映今天格论大大发展了的面貌,…”。那在此先简说此前全世界唯一的格论中文书(包括翻译的)并也是我曾认真读的日本Tadasi
Nakayama(中山正)的《格论》一书(中山正在这书“序”说‘格论的参考书一般有以下4本:即我的导师钟集先生的老师胡世华的导师Gottfried
Köthe的2本书和哈佛大学Garrett Birkhoff以及中山正的师兄Shokichi Iyanaga(弥永昌吉)各一本共4本书’。注:弥永昌吉主要从事数论,并如Eiichi Bannai在公开访谈录中就说这“弥永昌吉(Shokichi Iyanaga)教授,堪称日本数学之父”—弥永是这里Whitney之前的是国际数学教育委员会主席,他是Teiji Takagi高木贞治的博士,而还有更准确些的说法是“如果高木贞治是日本现代数学的‘生父’,那么弥永昌吉就是‘养父’”(可‘养父’弥永昌吉1906年才出生而上面海南琼州大学师爷黄际遇师1902年已去东京大学跟这“生父”高木贞治学习数学并1910年学成归国),而不论什么“父”-其意味着什么--小小日本不出国的数学家就获得2类都被誉为数学诺贝尔奖的菲尔茨奖3个、沃尔夫奖3个--而我们泱泱大中国至今还没获得1个仍待奋起直追,也如这里倒数第二段说日本现代数学以及日本最著名的数学大师几乎出自弥永昌吉和中山正及其门徒们,并在东京大学高木贞治指导下1935年获得博士的Tadasi
Nakayama中山正(同年去Osaka大学任教其后去美国、回名古屋等)50年代来到京都大学开创自己的数学王国并他的博士Masayoshi Nagata永田雅宜的博士Shigefumi Mori森重文获菲尔茨奖且已担任国际数学联盟主席(这是亚洲至今唯一的主席-此外某印度裔也担任过主席但他是在瑞士ETH
Zürich就职十年后才担任主席且其后一直在此就职),更因Shokichi Iyanaga(弥永昌吉)和Tadasi
Nakayama中山正的导师Teiji Takagi高木贞治是希尔伯特的高徒并这弥永昌吉、中山正和高木贞治师徒3人在数论的重要分支类域论的早期发展中都做出重要贡献,特别是弥永昌吉的博士岩泽创建的岩泽理论对世界三大猜想的解决起到关键作用)。上面中山正和他的博士及国际数学联盟主席徒孙3人都是京都大学的,关于该校也如这页或者这里第3个海南琼州大学的母校校长黄友谋的京都大学物理师兄弟也统治日本物理)。
再回来说我读研的1990年出版的《格论初步》,它的作者是解放前在中央研究院数学所师从陈省身、苏步青等、1950-1957年到北京大学数学系任教接着响应国家号召调往内蒙古大学任校长内蒙古政协副主席其后担任我们海南琼州大学的导师钟集为主席的委员的陈杰教授(关于陈杰教授可参考百度或刚见怀念良师益友陈杰先生说“文革后,陈杰先生致力于格论等研究,培养研究生,出版专著《格论初步》的“序言”说“鉴于在我国至今还没有一本国人编写的格论的著作”,并这专著荣获自治区优秀教学成果二等奖,在该省数学会更见海南琼州大学的导师担任主席的委员陈杰教授竟从1957年就担任该省数学会第一届理事长并一直担任到1990年-可能是我国最久的理事长其后第五届理事长才由1953年进北京大学数学曹之江校长担任、其后接任的理事长也是该省这重点大学校长陈国庆)。因中山正的《格论》由董克诚教授翻译在1964年已由上海科学技术出版社出版,而其后30年多年来发展的基本性的概念理论等肯定有必要成为新发展的基础,而且,这么长的这段时期国外也出版了一些紧跟新进展的外文基础性格论书,如此,才如陈杰教授所言有必要写一本附加其后诞生的理论的中文书。陈杰教授的这书后的参考书除中山正的上面《格论》外,还如陈杰教授说他最主要是参考George Grätzer在1978年出版的英文书《General
Lattice Theory一般格论》(这书作者George Grätzer的博士中徒子徒孙最多的2人Ivan Rival博士论文做‘组合数学格论’、Khee
Meng Koh博士论文做“组合数学”,这就是我们海南琼州大学攻读的中国第一个组合数学研究室的学科)。
象组合数学格论大师Robert
Dilworth的获得1993年计算机诺贝尔奖图灵奖的博士Juris
Hartmanis的博士论文就做“格论”,并我也有Juris
Hartmanis和同获1993年获图灵奖的Richard
Stearns合撰基于格论等且被图灵奖得主John
Hopcrof评论的《时序机的代数结构理论》(我只读这书的英文版-似乎还没中文版。在图论做许多工作的蔡进一是他的博士;第二作者Richard
Stearns的导师是在和我的导师开创树计数也是中国软件工程技术先驱这页见是多伦多大学校长图论大师Derek Corneil的研究生导师William Kahan(1989年图灵奖得主)。有篇中文图论论文和他俩的书同是时序机的:史维更,陈以农,时序机功能最小测试的图论方法,《计算机学报》1984年第3期,可参考该书引用的3篇论文:这博士论文及其师弟的论文和这论文).
格论不仅有深远的理论意义,其应用也具有极其重要而广泛作用如格代数结构最早是作为一种密码分析工具被引入密码学的.早在1982年,Adi
Shamir首次利用了格论对背包公钥密码算法进行了攻击(见Adi Shamir,A
polynomial time algorithm for breaking the Merkle-Hellman Cryptosystem,IEEE
Trans. Inf. Theory 30, 699-704
(1984) [最先于1982年会议]。看到这论文作者Adi Shamir,Applied Mathematics, Weizmann Institute of Science, Israel,就这Adi
Shamir正是计算机诺贝尔奖图灵奖得主。他的师侄Philippe
Flajolet是the Father of Analytic Combinatorics分析组合数学之父。分析组合数学是我们组合数学的一个年轻的新分支主要偏重算法,并Philippe
Flajolet的导师Jean Vuillemin和前面Adi Shamir是仅相差3年入学的师兄弟;Adi Shamir的导师Zohar
Manna和获得图灵奖的组合数学的海南琼大曾世界领先的哈密顿图的大师Robert
Tarjan也是仅相差3年入学的师兄弟).
更有,主要以海南琼州大学攻读的中国第一个组合数学研究室学科中的贡献知名的国际数学联盟主席László Lovász的格论码算法,至今仍是唯一已知能承受量子计算机攻击的加密系统基于的格论码算法(简称LLL法算)(或者说“目前唯一可以抵抗量子计算机攻击的加密系统就是基于他设计的
LLL 算法运行的”),就是他在1982年和Arjen
Lenstra、Hendrik Lenstra一起开发被广泛使用的Lattices-Based
Cryptography(格论密码)算法(常以这三个作者名简称为“LLL算法”(参考格基约化的LLL
(Lenstra-Lenstra-Lovász)算法,即来源于论文Arjen K. Lenstra, Hendrik W. Lenstra, Jr.; László Lovász, Factoring
polynomials
with rational coefficients. Math. Ann. 261 (1982), no. 4, 515--534.)。总之,基于格论的后量子密码具备抗量子攻击、易于硬件实现和用途广泛等诸多优势,已得到了国际学术界和工业界的广泛关注。(连续格本是因理论计算机问题的需要而由1976年图灵奖得主Dana S. Scott提出)
关于格论的参考资料,因格论主要属于代数学、又因它与组合数学以及数论有很深的渊源,如此除了上面中山正的“序”说它引用的4本格论书和陈杰教授的书引用的专论格论书外,格论不仅编入代数学方面的一些书籍:计算机鼻祖的导师我们组合数学先驱Marshall Hall, Jr.的世界名著《群伦》,国际数学联盟副主席Nathan
Jacobson的《抽象代数学》,以及A.Γ.库洛什的《一般代数学讲义》,美国科学院院长Saunders Mac Lane合写的《近世代数概论》下册;还编入组合数学方面的书籍:评价海南琼州大学士国内外一流水平的刘振宏大师翻译J. H. van Lint院士的《组合数学教程》,Richard
P. Stanley院士的《计数组合学》,János Pach和Pankaj
K. Agarwal合撰1995年出版的《Combinatorial
Geometry组合几何》第一章“数的几何”主要是讲“格”;以及编入数论方面的书籍:上面中山正是世界88而世界第7的André Weil的被认为是最难读的数论名著《Basic
number theory基础数论》的第二章等讲“格”,首位数学诺贝尔奖得主Carl
Ludwig Siege的《Lectures
on the geometry of numbers数的几何讲义》的第二、五章等讲“格”, 1974-1978年的英国皇家学会副主席(1978年前没有数学人担任主席)的J. W. S. Cassels在1997年出版的对1971年版《数的几何导论》的纠正重印版的第一章是“格”并他的导师Louis J.
Mordell评论这书等。上面所有这些书我都有来看看也曾有兴趣,不过,回海南后很艰难。
这些主要是经典格论。虽然,在上面陈杰校长出格论书之前我国格论的论文很少甚至1986年以前全国不到十篇但海南琼州大学的一个导师在1986年前已发表n维格的2篇论文--下面所述高维格论以海南琼大的这导师以及我们图论领域的知名专家János Pach和Pankaj
K. Agarwal合撰1995年出版的《Combinatorial
Geometry组合几何》一书等说之,如关于格:给定n维欧式空间Rn中的n个线性无关的向量(点)u1, u2, …,
un,这些向量生成的格Λ定义为
Λ(u1,
u2, …,
un)={ m1u1+ m2u2+ …+
mnun
|m1,m2,…,mnÎZ},其中Z是整数集。
称{u1,
u2, …,
un}为Λ的基。由形如m1u1+ m2u2+ …+
mnun(对每个i,miÎ{0,1})的2n的顶点导出的平行体P称为Λ的基本平行体或胞腔。并下面Minkowski的独有创见的基本结果,可以视为组合数学的鸽笼原理在可测集上的推广。…等等。
即其实,早先Minkowski注意到一个正定二次型确定了一个凸几何体和一个格, 他以天才的直觉证明了数的几何中里程碑式的基本结果: 如果\Rn中的一个关于原点对称的紧致凸几何体C之体积不小于2n,那么C必包含 一个非平凡(即非原点)整点. 令Λ⊂Rn为一个n维格, 关于Λ的Minkowski基本定理可以导出Λ中最短(非零)向量长度λ1(Λ)满足λ1(Λ) ≤ R, 如果以R为半径的球体积是2ndet(Λ), 其中det(Λ)是Rn /Λ的体积。在 2 和 3 维的情形下分别有 Lagrange 和
Gauss 的短向量长度的估计。然而, 当维数变量也被考虑时, 能否在多项式时间找到满足条件的非零格向量是个未知问题(就是经典格的大部分算法都是指数时间的,有的甚至是指数空间的,看百度的NTRU介绍见是其诞生的关键所在的出发点;还有最近向量问题, 不仅在密码学,它俩本身作为具有内在价值的数学问题本身, 以及作为在纯粹数学、应用数学等领域有强烈背景和需求的格归约问题, 从上面中山正以及陈杰教授的书知道长期以来一直以来备受重视, 不断有深入的研究)。当然,这个基本结果,也反映了数的几何等领域中凸体和格这两个最基本的概念之间的一个深刻关系。
(见书H. Minkowski,“Geometrie der Zahlen数的几何”. Leipzig:
Teubner, 1896.,海南琼州大学师爷叔Leonard.
E. Dickson评价H. Minkowski的这本书“Book Review: Geometrie der Zahlen”),如此,这页第3湖南省部分见哈密顿图先驱中的杨六泾Liow-Jing Yang,改名杨必中)的论文全是海南琼州大学曾居世界领先的哈密顿图,但美国的博士论文做“数的几何”,而因Minkowski的发现,如此“数的几何”领域的书籍都应编入格论的内容。可参考数的几何:www.qzu5.com/sj.htm;编码密码学:www.qzu5.com/ng.htm;更多相关领域参考www.qzu5.com/wl.htm 。
与组合数学密码学家靳蕃教授同是西南交大密码学领军专家的何大可教授(中国密码学会第一届正副理事长只有3人并是裴定一、冯登国、何大可)最近指导的这篇相关博士学位论文就做格理论应用于密码学的,也就是发展格理论密码学。并如“后量子安全的格公钥密码设计”博士论文开头说“人类似乎即将进入量子时代,后量子密码的研究越来越具有积极的理论意义和紧迫的现实意义.作为后量子密码的典型代表,近年来,格论公钥密码的研究持续升温”(后量子密码学,又称抗量子计算密码学,是专门研究能够抵抗量子计算机的加密算法,特别是公钥加密算法的密码学领域,)。正如百度对著名的公钥系统NTRU介绍说“NTRU是使用基于格论的加密算法来加密数据的公钥系统”“它的安全性依赖于格中最短向量问题。相对于离散对数或大数分解等公开秘密体制来说,它有许多优势。在安全性方面,NTRU算法具有抵抗量子计算攻击的能力,而RSA和ECC(elliptic curve cryptography)算法是无法抵抗量子计算的”。因而,已成为今天运算效率最高的格上密码系统之一,
并被认为是量子时代替换RSA和ECC的选项(RSA算法和ECC算法是目前最流行的主要的两种公钥加密算法--但在量子计算的框架下它俩都不能再提供安全保障,也就是随着量子计算机时代的来临其易于被攻破而使整个世界陷入不安全的危机处境之中,又由于近来量子算法和相关硬件发展进步,
因而如何设计能够抵御量子计算攻击的密码体系是当前备受关注的一个课题.
而基于格困难问题的密码体系被认为是最具有潜在抗量子特性的密码体系-也就是幸好有可代替它们的格论密码…)。
就如最近,美国国家标准与技术研究院 (NIST) 发起了一项国际竞赛,以寻找实现“后量子”密码学的最佳方法。评选出了第一批获胜者:四个参赛入围方案,其中有三个使用"格密码"。
其实就如前田周一郎(Shuichiro Maeda)早在1969年已出版《束论と量子理论》(即《格论和量子理论》)一书,可见格论和量子理论的关系早就显现出来。
与原子量子论的关系,还如我们组合数学的门徒就开创“引爆第四次工业革命”的量子计算;我们海南琼州大学曾居世界领先的哈密顿图也应用于原子核物理学,等等。
刚又见其发展出更多相关进展,在此附国内最近发表的可供参考的格密码领域的相关论文(其中杨连中教授是这页最后部分说他是海南琼州大学杂志编委的仪洪勋大师指导的博士):
即除了上面与组合数学密码学家靳蕃教授同单位的中国密码学会第一届副理事长指导的格密码领域博士论文,还有:
中国密码学会第一届理事长裴定一教授指导的量子纠错码的研究及构造,马智,中科大,博士2002年(关键词有“图论量子吗”-而这图论是海南琼州大学曾在一些领域居世界领先的学科);
中国密码学会第一届理事长裴定一教授指导的函数域上的格基约化算法和多序列线性反馈移位寄存器综合,王丽萍,中科大,博士2003年;
就如这篇“量子纠错编码若干问题的研究”博士学位论文说“图论方法构造出许多好的非二元量子码”;
山东大学杨连中教授指导的博士学位论文基于格的密码方案的研究与设计,蒋亚丽,山东大学,博士2011年;
RSA密码算法的格攻击技术研究,郑永辉,解放军信息工程大学,博士2009年
几类快速公钥密码的设计与分析,王保仓,西安电子科技大学,博士 2006年
格基规约理论及其在密码设计中的应用,余位驰,西南交通大学,博士2005年
我的导师钟集教授担任主席的委员陈杰教授指导的格论论文:二型Fuzzy集代数结构的若干性质,罗江涛,内蒙古大学学报(自然科学版) 1989-03-02。等等。