目錄
前言
第1章 集合論 1
1.1 基本概念 1
1.2 集合間的關(guān)系 3
1.3 集合的運(yùn)算 4
1.3.1 集合的基本運(yùn)算 4
1.3.2 集合的運(yùn)算律 7
1.3.3 例題 7
1.4 包含排斥原理 8
1.4.1 兩個(gè)集合的包含排斥原理 8
1.4.2 三個(gè)集合的包含排斥原理 10
1.4.3 多個(gè)集合的包含排斥原理 10
1.5 冪集合與笛卡兒積 13
1.5.1 冪集合 13
1.5.2 笛卡兒積 13
1.6 集合運(yùn)算與基數(shù)概念的擴(kuò)展 15
1.6.1 并集、交集的擴(kuò)展 15
1.6.2 基數(shù)概念的擴(kuò)展 16
1.7 習(xí)題 19
第2章 二元關(guān)系 23
2.1 基本概念 23
2.1.1 二元關(guān)系的定義 23
2.1.2 關(guān)系的運(yùn)算 24
2.2 一些特殊的關(guān)系 25
2.2.1 自反關(guān)系 25
2.2.2 對(duì)稱關(guān)系 25
2.2.3 傳遞關(guān)系 26
2.2.4 反自反關(guān)系 27
2.2.5 反對(duì)稱關(guān)系 27
2.3 復(fù)合關(guān)系 29
2.4 芙系的表示 31
2.4.1 用矩陣表示關(guān)系 31
2.4.2 用圖表示關(guān)系 32
2.4.3 特定關(guān)系的矩陣及其關(guān)系圖的屬性 33
2.4.4 復(fù)合關(guān)系的關(guān)系矩陣 36
2.5 逆關(guān)系 37
逆關(guān)系的性質(zhì) 38
2.6 關(guān)系的閉包 39
2.6.1 自反、對(duì)稱和傳遞閉包 39
2.6.2 閉包的性質(zhì)及求法 40
2.7 集合的劃分和覆蓋 44
2.7.1 劃分 44
2.7.2 交叉劃分 44
2.7.3 加細(xì) 45
2.8 等價(jià)關(guān)系與等價(jià)類 45
2.8.1 等價(jià)關(guān)系 45
2.8.2 等價(jià)類 47
2.8.3 劃分與等價(jià)關(guān)系 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 習(xí)題 61
第3章 同余與同余方裎 66
3.1 整數(shù)和除法 66
3.2 整數(shù) 66
3.3 素?cái)?shù) 68
3.4 最大公約數(shù)和最小公倍數(shù) 71
3.4.1 最大公約數(shù)和最小公倍數(shù)的定義 71
3.4.2 最大公約數(shù)和最小公倍數(shù)的求法 72
3.5 同余 73
同余定義及基本性質(zhì) 73
3.6 剩余系 74
3.6.1 完全剩余系 74
3.6.2 既約剩余系、Euler函數(shù)和Euler定理 76
3.7 歐拉函數(shù)的計(jì)算 77
3.8 一次同余方程 80
3.8.1 一次同余方程的概念 80
3.8.2 一次同余方程的解 81
3.9 剩余定理 82
3.9.1 一次同余方程組 82
3.9.2 剩余定理的計(jì)算機(jī)大整數(shù)加法 84
3.10 原根 86
3.10.1 原根的定義 86
3.10.2 具有原根的正整數(shù)的分布 90
3.11 指數(shù)的算術(shù) 99
3.12 原根在密碼學(xué)中的應(yīng)用 101
3.12.1 公鑰密碼學(xué)的背景知識(shí) 101
3.12.2 模重復(fù)平方計(jì)算方法 103
3.12.3 離散對(duì)數(shù)EIGamal公鑰加密方案 105
3.12.4 離散對(duì)數(shù)EIGamal公鑰簽名方案 107
3.12.5 EIGamal安全性討論 108
3.13 習(xí)題 109
第4章 二次剩余 112
4.1 模為合數(shù)的高次同余方程的解數(shù) 112
4.2 二次同余方程 117
4.3 勒讓德符號(hào) 12l
4.4 二次同余方程的求解 131
4.5 二次剩余的應(yīng)用 137
4.5.1 二次剩余在拋幣協(xié)議中的應(yīng)用 l37
4.5.2 二次剩余在零知識(shí)證明中的應(yīng)用 140
第5章 代數(shù)系統(tǒng)的基本知識(shí) 145
5.1 二元運(yùn)算及性質(zhì) 145
5.1.1 二元運(yùn)算的定義 145
5.1.2 二元運(yùn)算的性質(zhì) 146
5.2 代數(shù)系統(tǒng) l50
5.2.1 代數(shù)系統(tǒng)的定義與實(shí)例 150
5.2.2 代數(shù)系統(tǒng)的同構(gòu)與同態(tài) 151
5.3 習(xí)題 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 群在密碼學(xué)中的應(yīng)用 186
6.4.1 兩個(gè)特殊的群Zn和玩 186
6.4.2 Z和Euler定理 188
6.4.3 基于Z的公鑰密碼系統(tǒng)RSA 188
6.4.4 RSA的安全性討論 190
6.5 習(xí)題 191
第7章 環(huán)論 193
7.1 環(huán)的定義 193
7.2 環(huán)的同構(gòu)、子環(huán) 195
7.3 理想子環(huán) 197
7.4 習(xí)題 199
第8章 域 200
8.1 域的定義 200
8.2 子域 200
8.3 域的特征 201
8.4 域上的多項(xiàng)式環(huán) 202
8.5 域上多項(xiàng)式的帶余除法 203
8.6 多項(xiàng)式環(huán)的理想與商環(huán) 205
8.7 環(huán)與域在編碼糾錯(cuò)理論中的應(yīng)用 211
8.7.1 通信系統(tǒng)的基本模型 211
8.7.2 編碼理論的基本知識(shí) 212
8.7.3 線性分組碼的編碼與譯碼方案 219
8.7.4 線性分組碼的譯碼效率 227
8.7.5 循環(huán)碼的編碼與譯碼方案 229
8.7.6 循環(huán)碼的譯碼效率 238
8.8 習(xí)題 241
參考文獻(xiàn) 242