陈恭亮主编的这本《信息安全数学基础（第2版 ）》用统一的数学语言和符号系统地介绍了网络与信 息安全所涉及的数学理论和方法，特别是与三大难解 数学问题相关的数论、代数和椭圆曲线理论等，并对 一些重要算法作了详尽的推理和阐述。此外，还介绍 了网络与信息安全研究和应用中所产生的新的数学成 果。
本书可作为网络与信息安全专业、通信安全、计 算机安全和保密专业等的本科生和研究生的教学用书 ，也可以作为网络与信息安全的专业人员和从业人员 的参考用书。
引言
信息安全学科是一门新兴的学科 ,它涉及通信学、计算机科学、信息学和数学等多个学科,其中公钥密码学所基于的三个难解数学问题是:
(1)
大因数分解问题
(2)离散对数问题
(3)椭圆曲线离散对数问题.
这些问题涉及数论、代数和椭圆曲线论等 ,但应用于信息安全的数学理论和知识只是这些数学理论中的一小部分 ,而有关数论、代数和椭圆曲线论等方面的书籍多半是针对数学专业的学生的 .此外 ,在信息安全研究和应用中所产生的一些新的数学成果也没有在数论、代数和椭圆曲线论等教科书中体现.
作者自 2000年以来 ,在武汉大学数学系和计算机学院信息系以及上海交通大学信息安全工程学院给本科生和研究生相继开设了“数论与密码”、“椭圆曲线论”和“信息安全数学基础”等课程 ,深知学生在学习与信息安全相关的数学知识 ,特别是关于数论、代数和椭圆曲线论等数学知识的过程中所遇到的困难 .因此 ,希望将这些应用于信息安全的数学理论作一次较系统的介绍 ,以方便信息安全专业、数学系、计算机学院、通信工程系等学生以及信息安全方面的工作者学习.
本书在编写过程中得到了上海交通大学信息安全工程学院及武汉大学数学系和计算机学院信息系许多教师以及本科生和研究生的支持和帮助 ,在此向他们表示衷心的感谢 .此外 ,特别感谢姚家燕、周超勇和沈丽敏的许多具体帮助 .另外 ,特别感谢国家自然科学基金青年基金 (项目编号: 19501032)和国家教委优秀青年教师基金的支持.
陈恭亮 2004年 2月
第 2版引言
本书自 2004年 6月出版后，在上海交通大学、武汉大学、西安电子科技大学、北京电子技术学院、杭州电子科技大学等几十所高校使用 .许多教师和学生提出了很多宝贵建议 .作者根据这些建议，面向传统教学和远程教学、视频课程教学、 MOOC课程教学和“翻转式”课堂教学等，以及信息安全专业学生、网络和信息安全从业人员对网络和信息安全的数学理论和方法的需求，结合网络与信息安全技术的最新进展，以及“信息安全数学基础”课程教学经验的积累，特别是“发现、学习、寻求、解决、提升”的教学理念，对本书作了一些修订 .
(1)基础性
:对网络和信息安全所涉及的数学理论和方法及重要算法给出了详细的推理和说明.
(2)系统性
:用统一的数学语言和符号来将三大数学难题、网络和信息安全所涉及的散落在数论、代数、椭圆曲线三方面的数学知识形成系统的知识体系 .
(3)前沿性:密切跟踪国际上的信息安全和密码算法标准，并给出详细阐述 .
(4)重构性
:对定理及例题作了更有序的编号 ,使得一些知识可以构成独立的知识体系 ,以满足网络和信息安全专业人员和非专业人员对相关知识的学习和掌握.
(5)专业性
:对一些数学符号和语言作了更系统的表述 ,以满足网络和信息安全专业人员和非专业人员对相关知识的进一步学习和掌握.
(6)工程性
:对一些重要定理及应用作了更详细的阐述 ,以满足网络和信息安全专业人员和非专业人员对相关工程实现和创新应用的需求.
发现 :就是要发现信息化推进中不断提出的网络和信息安全问题 (如国际密码标准 P1363，密码技术、 RSA、Di.e-Hellman密钥协商、 ECC、AES、物联网安全、轻量级密码技术、身份认证鉴别、认证加密和身份管理等 )以及国内外相关信息通信技术的新进展.
学习 :就是要学习该课程所涉及的基本数学理论和方法 ,如学习与三大难解数学问题 (大整数分解问题、离散对数问题、椭圆曲线离散对数问题 )相关的整数理论、同余理论、代数理论、椭圆曲线理论等 .
寻求 :就是要寻求关于网络和信息安全问题的应用技术 ,如广义欧几里得除法、中国剩余定理、欧拉定理、大素数生成、有限域的构造、 Galois域等.解决 :就是要运用基本理论和方法，以及应用技术解决信息安全的工程问题 ,如公钥加密/解密、密钥协商等 .提升 :就是要在发现、学习、寻求、解决的过程中提升科学素养，进而发现更深层的信息安全问题并提高学习和创新能力.
陈恭亮 2014年 2月于巴黎
第1章 整数的可除性
1.1 整除的概念、欧几里得除法
1.1.1 整除的概念
1.1.2 Eratoshenes筛法
1.1.3 欧几里得除法 ——最小非负余数
1.1.4 素数的平凡判别
1.1.5 欧几里得除法 ——一般余数
1.2 整数的表示
1.2.1 b进制
1.2.2 计算复杂性
1.3 最大公因数与广义欧几里得除法
1.3.1 最大公因数
1.3.2 广义欧几里得除法及计算最大公因数
1.3.3 B′ezout等式
1.3.4 B′ezout等式的证明
1.3.5 最大公因数的进一步性质
1.3.6 多个整数的最大公因数及计算
1.3.7 形为 2a1的整数及其最大公因数
1.4 整除的进一步性质及最小公倍数
1.4.1 整除的进一步性质
1.4.2 最小公倍数
1.4.3 最小公倍数与最大公因数
1.4.4 多个整数的最小公倍数
1.5 整数分解
1.6 素数的算术基本定理
1.6.1 算术基本定理
1.6.2 算术基本定理的应用
1.7 素数定理
1.8 习题
第2章 同余
2.1 同余的概念及基本性质
2.1.1 同余的概念
2.1.2 同余的判断
2.1.3 同余的性质
2.2 剩余类及完全剩余系
2.2.1 剩余类与剩余
2.2.2 完全剩余系
2.2.3 两个模的完全剩余系
2.2.4 多个模的完全剩余系
2.3 简化剩余系与欧拉函数
2.3.1 欧拉函数
2.3.2 简化剩余类与简化剩余系
2.3.3 两个模的简化剩余系
2.3.4 欧拉函数的性质
2.4 欧拉定理、费马小定理和 Wilson定理
2.4.1 欧拉定理
2.4.2 费马小定理
2.4.3 Wilson定理
2.5 模重复平方计算法
2.6 习题
第3章 同余式
3.1 基本概念及一次同余式
3.1.1 同余式的基本概念
3.1.2 一次同余式
3.2 中国剩余定理
3.2.1 中国剩余定理：“物不知数”与韩信点兵
3.2.2 两个方程的中国剩余定理
3.2.3 中国剩余定理之构造证明
3.2.4 中国剩余定理之递归证明
3.2.5 中国剩余定理之应用 ——算法优化
3.3 高次同余式的解数及解法
3.3.1 高次同余式的解数
3.3.2 高次同余式的提升
3.3.3 高次同余式的提升 ——具体应用
3.4 素数模的同余式
3.4.1 素数模的多项式欧几里得除法
3.4.2 素数模的同余式的简化
3.4.3 素数模的同余式的因式分解
3.4.4 素数模的同余式的解数估计
3.5 习题
第4章 二次同余式与平方剩余
4.1 一般二次同余式
4.2 模为奇素数的平方剩余与平方非剩余
4.3 勒让得符号
4.3.1 勒让得符号之运算性质
4.3.2 高斯引理
4.4 二次互反律
4.5 雅可比符号
4.6 模平方根
4.6.1 模 p平方根
4.6.2 模 p平方根
4.6.3 模 m平方根
4.7 x2
4.8 习题
第5章 原根与指标
5.1 指数及其基本性质
5.1.1 指数
5.1.2 指数的基本性质
5.1.3 大指数的构造
5.2 原根
5.2.1 模 p原根
5.2.2 模 pα原根
5.2.3 模 2α指数
5.2.4 模 m原根
5.3 指标及 n次同余式
5.3.1 指标
5.3.2 n次同余式
5.4 习题
第6章 素性检验
6.1 伪素数
6.1.1 伪素数 Fermat素性检验
6.1.2 无穷多伪素数
6.1.3 平方因子的判别
6.1.4 Carmicheal数
6.2 Euler伪素数
6.2.1 Euler伪素数、Solovay-Stassen素性检验
6.2.2 无穷多 Euler伪素数
6.3 强伪素数
6.3.1 强伪素数、Miller-Rabin素性检验
6.3.2 无穷多强伪素数
6.4 习题
第7章 连分数
7.1 简单连分数
7.1.1 简单连分数构造
7.1.2 简单连分数的渐近分数
7.1.3 重要常数e,π,γ的简单连分数
7.2 连分数
7.2.1 基本概念及性质
7.2.2 连分数的渐近分数
7.3 简单连分数的进一步性质
7.4 最佳逼近
7.5 循环连分数
7.6 √ n与因数分解
7.7 习题
第8章 群
8.1 群
8.1.1 基本定义
8.1.2 子群
8.2 正规子群和商群
8.2.1 陪集的拉格朗日定理
8.2.2 陪集的进一步性质
8.2.3 正规子群和商群
8.3 同态和同构
8.3.1 基本概念
8.3.2 同态分解定理
8.3.3 同态分解定理的进一步性质
8.4 习题
第9章 群的结构
9.1 循环群
9.1.1 循环群
9.1.2 循环子群的构造
9.2 有限生成交换群
9.3 置换群
9.4 习题
第10章 环与理想
10.1 环
10.1.1 基本定义
10.1.2 零因子环
10.1.3 整环及域
10.1.4 交换环上的整除
10.2 同态
10.3 特征及素域
10.4 分式域
10.5 理想和商环
10.5.1 理想
10.5.2 商环
10.5.3 环同态分解定理
10.6 素理想
10.7 习题
第11章 多项式环
11.1 多项式整环
11.2 多项式整除与不可约多项式
11.3 多项式欧几里得除法
11.4 多项式同余
11.5 本原多项式
11.6 多项式理想
11.7 多项式结式与判别式
11.8 习题
第12章 域和 Galois理论
12.1 域的扩张
12.1.1 域的有限扩张
12.1.2 域的代数扩张
12.2 Galois基本定理
12.2.1 K-同构
12.2.2 Galois基本定理概述
12.2.3 基本定理之证明
12.3 可分域、代数闭包
12.3.1 可分域
12.3.2 代数闭包
12.4 习题
第13章 域的结构
13.1 超越基
13.2 有限域的构造
13.3 有限域的 Galois群
13.3.1 有限域的 Frobenius映射
13.3.2 有限域的 Galois群概述
13.4 正规基
13.5 习题
第14章 椭圆曲线
14.1 椭圆曲线基本概念
14.2 加法原理
14.2.1 实数域 R上椭圆曲线
14.2.2 素域 Fp (p> 3)上的椭圆曲线 E
14.2.3 域 F2n (n》1)上的椭圆曲线 E, j(E)=0
14.3 有限域上的椭圆曲线的阶
14.4 重复倍加算法
14.5 习题
第15章 AKS素性检验
附录A 三个数学难题
附录B 周期序列
附录C 前1280个素数及其原根表
附录D F359
D.1 域F359中生成元g=7的幂指表：由k得到h=gk
D.2 域F359中生成元g=7的指数表：由h得到gk=h
附录E F28=F2[x]/(x8+x4+x3+x2+1)
E.1 域中生成元g=x的幂指表：由k得到h=gk
E.2 域中生成元g=x的指数表：由h得到gk=h
E.3 域中生成元g=x的幂的函数u2+u表：由k得到h=g2k+gk
E.4 域中生成元g=x的广义指数表：由h得到g2k+gk=h
附录F F28=F2[x]/(x8+x4+x3+x+1)
F.1 域中生成元g=x+1的幂指表：由k得到h=gk
F.2 域中生成元g=x+1的指数表：由h得到gk=h
F.3 域中生成元g=x+1的幂的函数u2+u表：由k得到h=g2k+gk
F.4 域中生成元g=x+1的广义指数表：由h得到g2k+gk=h
索引
参考文献
书单推荐
