第1章 数论基础 1
1.1 素数与带余除法 1
1.1.1 素数 1
1.1.2 带余除法 2
1.2 最大公因子与辗转相除法 2
1.3 模运算与同余 4
1.3.1 模运算 4
1.3.2 同余 5
1.3.3 欧拉定理 6
1.4 同余方程 8
1.5 中国剩余定理 9
1.6 数论在密码学中的应用 11
1.6.1 密码学的基本概念 11
1.6.2 移位密码 13
1.6.3 多表代换密码 13
1.6.4 多字母代换密码 14
1.6.5 同余方程与仿射密码 15
1.6.6 中国剩余定理与密钥的分散管理 16
本章小结 18
本章习题 18
第2章 群 19
2.1 关系与等价关系 19
2.1.1 关系 19
2.1.2 等价关系 20
2.2 运算与同态 21
2.2.1 运算 21
2.2.2 同态映射 23
2.3 群的定义与性质 24
2.3.1 半群与含幺半群 24
2.3.2 群 25
2.4 子群与群的同态 28
2.4.1 子群 28
2.4.2 群的同态 29
2.5 循环群 30
2.6 陪集与正规子群 32
2.6.1 陪集 32
2.6.2 正规子群 33
2.6.3 群同态基本定理 36
2.7 群与纠错编码 37
2.7.1 线性分组码与汉明重量 38
2.7.2 线性码的生成矩阵与校验矩阵 41
2.7.3 陪集与译码方法 44
本章小结 47
本章习题 47
第3章 环 49
3.1 环的定义及其性质 49
3.1.1 环的定义 49
3.1.2 环的性质 51
3.1.3 整环 52
3.1.4 除环 53
3.2 子环和环的同态 56
3.2.1 子环的概念 56
3.2.2 环的同态 57
3.3 环的直积、矩阵环、多项式环、序列环 58
3.3.1 环的直积与矩阵环 58
3.3.2 多项式环与序列环 59
3.4 理想与环同态基本定理 62
3.4.1 理想 63
3.4.2 环同态基本定理 64
3.5 环在信息安全中的应用 67
3.5.1 拉格朗日插值与密钥的分散管理 67
3.5.2 同态加密体制 69
本章小结 74
本章习题 74
第4章 域 75
4.1 分式域 75
4.2 扩域 77
4.3 多项式的分裂域 82
4.4 域的特征和有限域的结构 88
4.5 有限域上的离散对数与密钥交换协议 93
本章小结 95
本章习题 95
第5章 数理逻辑基础 97
5.1 命题逻辑 97
5.1.1 命题与联结词 97
5.1.2 命题公式及其赋值 100
5.2 命题逻辑等值演算与推理 103
5.2.1 等值式 103
5.2.2 析取范式与合取范式 106
5.2.3 联结词的完备集 109
5.2.4 命题逻辑的推演系统 111
5.3 一阶逻辑 113
5.3.1 一阶逻辑的基本概念 113
5.3.2 一阶逻辑公式及其解释 115
5.3.3 一阶逻辑的等值演算与前束范式 117
5.3.4 一阶逻辑的推理理论 118
5.4 数理逻辑在信息安全中的应用 120
5.4.1 模态逻辑 120
5.4.2 数理逻辑在安全协议分析中的初步应用 121
本章小结 125
本章习题 126
第6章 图论基础 128
6.1 基本概念 128
6.1.1 图的定义 128
6.1.2 完全图和正则图 130
6.1.3 子图 131
6.2 通路与同路 132
6.3 图的矩阵表示 134
6.4 欧拉图与汉密尔顿图 135
6.5 树与生成树 139
6.6 图论在信息安全中的应用 143
6.6.1 图的同构 143
6.6.2 基于同构图的零知识证明系统 144
本章小结 145
本章习题 145