目錄
前言
第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 集合運算與基數(shù)概念的擴展 15
1.6.1 并集、交集的擴展 15
1.6.2 基數(shù)概念的擴展 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 函數(shù) 58
2.10.1 函數(shù)的定義 58
2.10.2 函數(shù)的合成 59
2.10.3 特殊函數(shù)類 60
2.11 習題 61
第3章 同余與同余方裎 66
3.1 整數(shù)和除法 66
3.2 整數(shù) 66
3.3 素數(shù) 68
3.4 最大公約數(shù)和最小公倍數(shù) 71
3.4.1 最大公約數(shù)和最小公倍數(shù)的定義 71
3.4.2 最大公約數(shù)和最小公倍數(shù)的求法 72
3.5 同余 73
同余定義及基本性質 73
3.6 剩余系 74
3.6.1 完全剩余系 74
3.6.2 既約剩余系、Euler函數(shù)和Euler定理 76
3.7 歐拉函數(shù)的計算 77
3.8 一次同余方程 80
3.8.1 一次同余方程的概念 80
3.8.2 一次同余方程的解 81
3.9 剩余定理 82
3.9.1 一次同余方程組 82
3.9.2 剩余定理的計算機大整數(shù)加法 84
3.10 原根 86
3.10.1 原根的定義 86
3.10.2 具有原根的正整數(shù)的分布 90
3.11 指數(shù)的算術 99
3.12 原根在密碼學中的應用 101
3.12.1 公鑰密碼學的背景知識 101
3.12.2 模重復平方計算方法 103
3.12.3 離散對數(shù)EIGamal公鑰加密方案 105
3.12.4 離散對數(shù)EIGamal公鑰簽名方案 107
3.12.5 EIGamal安全性討論 108
3.13 習題 109
第4章 二次剩余 112
4.1 模為合數(shù)的高次同余方程的解數(shù) 112
4.2 二次同余方程 117
4.3 勒讓德符號 12l
4.4 二次同余方程的求解 131
4.5 二次剩余的應用 137
4.5.1 二次剩余在拋幣協(xié)議中的應用 l37
4.5.2 二次剩余在零知識證明中的應用 140
第5章 代數(shù)系統(tǒng)的基本知識 145
5.1 二元運算及性質 145
5.1.1 二元運算的定義 145
5.1.2 二元運算的性質 146
5.2 代數(shù)系統(tǒng) l50
5.2.1 代數(shù)系統(tǒng)的定義與實例 150
5.2.2 代數(shù)系統(tǒng)的同構與同態(tài) 151
5.3 習題 155
第6章 群論 157
6.1 半群 157
6.2 單位元和逆元 158
6.3 群 162
6.3.1 群的定義 162
6.3.2 群的同態(tài) 165
6.3.3 循環(huán)群 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和玩 186
6.4.2 Z和Euler定理 188
6.4.3 基于Z的公鑰密碼系統(tǒng)RSA 188
6.4.4 RSA的安全性討論 190
6.5 習題 191
第7章 環(huán)論 193
7.1 環(huán)的定義 193
7.2 環(huán)的同構、子環(huán) 195
7.3 理想子環(huán) 197
7.4 習題 199
第8章 域 200
8.1 域的定義 200
8.2 子域 200
8.3 域的特征 201
8.4 域上的多項式環(huán) 202
8.5 域上多項式的帶余除法 203
8.6 多項式環(huán)的理想與商環(huán) 205
8.7 環(huán)與域在編碼糾錯理論中的應用 211
8.7.1 通信系統(tǒng)的基本模型 211
8.7.2 編碼理論的基本知識 212
8.7.3 線性分組碼的編碼與譯碼方案 219
8.7.4 線性分組碼的譯碼效率 227
8.7.5 循環(huán)碼的編碼與譯碼方案 229
8.7.6 循環(huán)碼的譯碼效率 238
8.8 習題 241
參考文獻 242