《初等数论及其在信息科学中的应用》是一本关于初等数论及其在密码学中应用的基础教材。全书共分5章。第1章和第2章分别介绍整除性和同余理论。第3章讨论前两章知识在古典密码学和RSA公钥密码体制中的应用。第4章介绍二次剩余及其在硬币抛掷和零知识证明中的应用。第5章介绍阶、原根和离散对数的概念及其在伪随机数生成、ElGamal公钥密码体制和椭圆曲线密码中的应用。每章后面都配有习题,书末附有习题答案及提示。另外,在附录中,我们按照章节顺序列出了两种常用数学软件Maple和Mathematica用于数论计算的有关命令。
《初等数论及其在信息科学中的应用》可以作为综合性和工科院校数学专业和信息科学相关专业的初等数论本科生课程教材,也可作为相关领域中的教学科研人员以及工程技术人员的参考书。
《初等数论及其在信息科学中的应用》以经典理论与现代应用相结合的方式,比较系统地介绍了初等数论的基本概念和方法。具体内容包括模为素数的高次同余方程、密码学基本概念、RSA的安全性讨论、ElGamal密码体制、椭圆曲线密码等。该书可供各大专院校作为教材使用,也可供从事相关工作的人员作为参考用书使用。
数论是研究数的规律,特别是整数性质的数学分支,而初等数论主要是用整数的四则运算方法研究整数性质的数论分支,它是数学中最古老的分支之一.著名数学家哈代(G.H.Hardy)说过,“初等数论应当是一种极好的早期数学教育素材.它需要的预备知识很少,材料很实在,可以触摸得到,又为人们所熟悉;它所用的推理过程非常简单,有普遍意义,而且为数不多;在数学科学中它非常独特,因为它能激发人们的天然好奇心.花上一个月的时光,进行富有智慧的数论启蒙教育,它将会带来双倍效益,双倍作用,比起同等数量的给工程技术人员上的微积分来说,更将是十倍地有趣.”
近几十年来,初等数论在物理学、化学、生物学、计算机科学、密码学、编码理论、数字信息和电气工程等领域得到了广泛而深入的应用,以至于华盛顿大学布兰克(B.E.Blank)教授曾说:“现今如果你教一门数论课程,计算机专业的学生很可能比数学专业的学生更感兴趣.许多人较少关心能被表成两个平方和的整数,但更关心Alice如何与Bob进行保密通信.”
基于初等数论的上述特点和教学的需要,本书以经典理论与现代应用相结合的方式,比较系统地介绍了初等数论的基本概念和方法.本书的写作目的是双重的:一是希望能使数学专业的学生在掌握初等数论基本概念的同时,体会到这些概念和结果在信息科学,特别是密码学中的应用价值,从而激发他们对数论的学习兴趣;二是希望通过初等数论在信息科学中的具体应用,帮助信息科学相关专业的学生克服害怕数学的心理,理解并掌握初等数论的基本概念,为“密码学”和“信息安全”等课程奠定基础.本书的初稿内容曾多次在北京大学(曹永知副教授主讲)和北京邮电大学(作者主讲)为计算机专业、通信专业和应用数学专业的学生讲授过,均收到了良好效果.
在本书的编写过程中,我们力求系统性、实用性和可读性相结合.系统性方面,就初等数论本身而言,本书覆盖了它的基本知识;就应用而言,我们介绍了几种常见的古典密码体制和目前公认为安全的三种公钥密码体制.实用性方面,由于课时的限制,我们尽量选取初等数论中有较强应用背景的知识和有代表性的例子.为了增强本书的可读性,书中大多由浅入深地介绍概念和性质,同时也注意介绍概念的由来及相互之间的联系.在附录中,我们列出了两种常用数学软件Maple和Mathematica用于数论计算的有关命令,为读者使用计算机计算数论函数(尤其是进行有关涉及大整数的计算)提供了方便.本书绝大多数内容只需要读者具有中学数学知识便可领会,当然,了解一点概率论、数学分析、抽象代数和计算复杂性知识对于深入理解本书内容也是十分有益的.
本书可以作为综合性和工科院校数学专业及信息科学相关专业的初等数论本科生课程教材,建议授课32~48学时.同时,也可作为相关领域中的教学、科研人员以及工程技术人员的参考书.
曹永知副教授在使用本书初稿时提出了不少修改意见,谨此表示谢意.本书的出版还得到了国家自然科学基金的资助,基金号:61070251.正如潘承洞先生和潘承彪先生所言,“要写好一本初等数论的教材绝非易事.”由于水平有限,书中难免存在不妥之处,敬请读者批评指正.
作者
第1章 整除性
1.1 整除
1.2 最大公因数与欧几里得算法
1.3 最小公倍数
1.4 一次不定方程
1.5 算术基本定理
1.6 厄拉多塞筛法
1.7 素数分布
习题一
第2章 同余
2.1 同余定义及基本性质
2.2 剩余系
2.3 欧拉函数与默比乌斯函数
2.4 一次同余方程
2.5 中国剩余定理
2.6 模为素数的高次同余方程
2.7 模为合数的高次同余方程
2.8 伪素数和素性测试
习题二
第3章 RSA密码体制
3.1 密码学基本概念
3.2 几种简单密码体制及其破译
3.3 RSA公钥密码体制
3.4 RSA的实现
3.5 RSA的安全性讨论
习题三
第4章 二次剩余
4.1 概念及判别
4.2 勒让德符号
4.3 二次同余方程
4.4 雅可比符号
4.5 二次剩余的应用
习题四
第5章 原根及其应用
5.1 整数的阶
5.2 原根
5.3 一般既约剩余系的构造
5.4 离散对数
5.5 伪随机数
5.6 ElGamal密码体制
5.7 椭圆曲线密码
习题五
附录A 抽象代数基本概念
附录B 数学软件Maple和Mathematica中的一些与数论相关的命令
B.1 Maple中的一些与数论相关的命令
B.2 Mathematica中的一些与数论相关的命令
习题答案及提示
索引
参考文献