第1章 集合论 1
1.1 基本概念 1
1.2 集合间的关系 3
1.3 集合的运算 4
1.3.1 集合的基本运算 4
1.3.2 集合的运算律 7
1.3.3 例题 7
1.4 包含排斥原理 8
1.4.1 两个集合的包含排斥原理 8
1.4.2 三个集合的包含排斥原理 10
1.4.3 多个集合的包含排斥原理 10
1.5 幂集合与笛卡儿积 13
1.5.1 幂集合 13
1.5.2 笛卡儿积 13
1.6 集合运算与基数概念的扩展 15
1.6.1 并集、交集的扩展 15
1.6.2 基数概念的扩展 16
1.7 习题 19
第2章 二元关系 23
2.1 基本概念 23
2.1.1 二元关系的定义 23
2.1.2 关系的运算 24
2.2 一些特殊的关系 25
2.2.1 自反关系 25
2.2.2 对称关系 25
2.2.3 传递关系 26
2.2.4 反自反关系 27
2.2.5 反对称关系 27
2.3 复合关系 29
2.4 关系的表示 31
2.4.1 用矩阵表示关系 31
2.4.2 用图表示关系 32
2.4.3 特定关系的矩阵及其关系图的属性 33
2.4.4 复合关系的关系矩阵 36
2.5 逆关系 37
逆关系的性质 38
2.6 关系的闭包 39
2.6.1 自反、对称和传递闭包 39
2.6.2 闭包的性质及求法 40
2.7 集合的划分和覆盖 44
2.7.1 划分 44
2.7.2 交叉划分 44
2.7.3 加细 45
2.8 等价关系与等价类 45
2.8.1 等价关系 45
2.8.2 等价类 47
2.8.3 划分与等价关系 48
2.9 偏序 49
2.9.1 引言 49
2.9.2 字典顺序 52
2.9.3 哈斯图 54
2.9.4 极大元素与极小元素 55
2.9.5 格 57
2.10 函数 58
2.10.1 函数的定义 58
2.10.2 函数的合成 59
2.10.3 特殊函数类 60
2.11 习题 61
第3章 同余与同余方程 66
3.1 整数和除法 66
3.2 整数 66
3.3 素数 68
3.4 最大公约数和最小公倍数 71
3.4.1 最大公约数和最小公倍数的定义 71
3.4.2 最大公约数和最小公倍数的求法 72
3.5 同余 73
同余定义及基本性质 73
3.6 剩余系 74
3.6.1 完全剩余系 74
3.6.2 既约剩余系、Euler函数和Euler定理 76
3.7 欧拉函数的计算 77
3.8 一次同余方程 80
3.8.1 一次同余方程的概念 80
3.8.2 一次同余方程的解 81
3.9 剩余定理 82
3.9.1 一次同余方程组 82
3.9.2 剩余定理的计算机大整数加法 84
3.10 原根 86
3.10.1 原根的定义 86
3.10.2 具有原根的正整数的分布 90
3.11 指数的算术 99
3.12 原根在密码学中的应用 101
3.12.1 公钥密码学的背景知识 101
3.12.2 模重复平方计算方法 103
3.12.3 离散对数ElGamal公钥加密方案 105
3.12.4 离散对数ElGamal公钥签名方案 107
3.12.5 ElGamal安全性讨论 108
3.13 习题 109
第4章 二次剩余 112
4.1 模为合数的高次同余方程的解数 112
4.2 二次同余方程 117
4.3 勒让德符号 121
4.4 二次同余方程的求解 131
4.5 二次剩余的应用 137
4.5.1 二次剩余在抛币协议中的应用 137
4.5.2 二次剩余在零知识证明中的应用 140
第5章 代数系统的基本知识 145
5.1 二元运算及性质 145
5.1.1 二元运算的定义 145
5.1.2 二元运算的性质 146
5.2 代数系统 150
5.2.1 代数系统的定义与实例 150
5.2.2 代数系统的同构与同态 151
5.3 习题 155
第6章 群论 157
6.1 半群 157
6.2 单位元和逆元 158
6.3 群 162
6.3.1 群的定义 162
6.3.2 群的同态 165
6.3.3 循环群 168
6.3.4 变换群 171
6.3.5 置换群 174
6.3.6 子群 178
6.3.7 子群的陪集 181
6.3.8 不变子群和商群 184
6.4 群在密码学中的应用 186
6.4.1 两个特殊的群Zn和Z＊n 186
6.4.2 Z＊n和Euler定理 188
6.4.3 基于Z＊n的公钥密码系统RSA 188
6.4.4 RSA的安全性讨论 190
6.5 习题 191
第7章 环论 193
7.1 环的定义 193
7.2 环的同构、子环 195
7.3 理想子环 197
7.4 习题 199
第8章 域 200
8.1 域的定义 200
8.2 子域 200
8.3 域的特征 201
8.4 域上的多项式环 202
8.5 域上多项式的带余除法 203
8.6 多项式环的理想与商环 205
8.7 环与域在编码纠错理论中的应用 211
8.7.1 通信系统的基本模型 211
8.7.2 编码理论的基本知识 212
8.7.3 线性分组码的编码与译码方案 219
8.7.4 线性分组码的译码效率 227
8.7.5 循环码的编码与译码方案 229
8.7.6 循环码的译码效率 238
8.8 习题 241
参考文献 242