內容簡介
本書從實用角度出發，介紹數論的有關基礎理論、實用算法及其套用。全書共9章，主要內容包括整數的可除性、數論函式、同餘及其運算、同餘方程、二次同餘方程與平方剩餘、原根與離散對數、連分數、素性測試和整數分解、有限域等。本書選材精練，推理嚴謹，重點突出，例題豐富，習題難易適度，對重點內容從不同角度進行論述，尤其對實用問題舉例較多，有利於培養讀者利用數論的理論和方法解決實際問題的能力。本書可作為計算機、通信、信息和網路安全、數學等專業的研究生教材，也可作為相關領域科研人員的參考書。
目錄
第 1 章 整數的可除性 1
1.1 整除的概念與帶餘除法 1
1.1.1 整除及其性質 1
1.1.2 素數 4
1.1.3 帶餘除法 5
1.2 整數的表示 7
1.3 最大公因數與輾轉相除法 8
1.3.1 最大公因數 8
1.3.2 輾轉相除法 13
1.3.3 求（a，b）的算法 14
1.3.4 （a，b）與a、b的關係 17
1.3.5 其他性質 22
1.4 整除的進一步性質及最低公倍數 25
1.4.1 整除和最大公因數的其他性質 25
1.4.2 最低公倍數及其性質 26
1.5 算術基本定理 28
習題1 32
第 2 章 數論函式 38
2.1 數論函式 38
2.2 函式x|、 |x 、 [x] 38
2.2.1 下整數函式x| 38
2.2.2 上整數函式|x 39
2.2.3 四捨五入函式[x] 39
2.3 函式potpn 40
2.4 Euler函式φ(n) 43
2.5 墨比烏斯函式μ(n) 50
2.5.1 墨比烏斯函式 50
2.5.2 墨比烏斯反演公式 53
2.6 素數個數函式π(n) 56
2.7 數論函式的狄利克雷乘積 57
2.8 積性函式 60
2.8.1 積性函式的定義 61
2.8.2 積性函式的性質 62
習題2 65
第 3 章 同餘及其運算 71
3.1 同餘的概念及基本性質 71
3.2 剩餘類及完全剩餘系 77
3.2.1 剩餘類和完全剩餘系 77
3.2.2 剩餘類的性質 79
3.3 既約剩餘系 80
3.3.1 既約剩餘系 80
3.3.2 整數a模m的逆 84
3.4 歐拉定理和費馬小定理 87
3.4.1 歐拉定理 87
3.4.2 費馬小定理 89
3.5 模重複平方計算法 91
3.5.1 算法原理 91
3.5.2 模重複平方計算法 92
3.6 一次不定方程 95
3.6.1 二元一次（不定）方程 95
3.6.2 求特解的方法 99
3.6.3 s元一次不定方程 103
3.6.4 （s元）一次不定方程組 104
3.7 矩陣的同餘運算 107
3.7.1 矩陣及其線性運算 107
3.7.2 矩陣乘法 109
3.7.3 可逆矩陣 111
3.8 同餘的套用 113
3.8.1 RSA公鑰密碼算法 113
3.8.2 背包公鑰密碼算法 114
3.8.3 希爾密碼算法 116
3.8.4 隨機數的Lehmer生成算法 118
3.8.5 隨機數的BBS生成算法 120
習題3 121
第 4 章 同餘方程 126
4.1 基本概念 126
4.2 一次同餘方程 134
4.3 中國剩餘定理 140
4.4 高次同餘方程的解數及解法 152
4.4.1 解數 152
4.4.2 特殊情形的解法 154
4.4.3 一般情形的解法 161
4.5 素數模的同餘方程 165
4.5.1 同餘方程的化簡 165
4.5.2 解數的判斷 168
4.6 同餘方程的套用 170
4.6.1 密鑰分存 170
4.6.2 資料庫加密方案 173
4.6.3 BBS流密碼算法 174
習題4 177
第 5 章 二次同餘方程與平方剩餘 182
5.1 一般二次同餘方程 182
5.1.1 二次同餘方程的化簡 182
5.1.2 平方剩餘 183
5.2 模為奇素數的平方剩餘與平方非剩餘 185
5.2.1 平方剩餘的判斷條件 185
5.2.2 平方剩餘的個數 187
5.3 勒讓德符號 188
5.4 雅可比符號 198
5.5 模p平方根 205
5.6 模數為合數的情形 209
5.6.1 p為奇素數 210
5.6.2 p=2 210
5.7 解同餘方程小結 215
習題5 215
第 6 章 原根與離散對數 221
6.1 整數的階及其性質 221
6.1.1 整數的階和原根 221
6.1.2 階的性質與計算方法 222
6.2 原根的存在性與計算方法 235
6.3 離散對數 244
6.4 離散對數的計算 247
6.4.1 Pohlid-Hellman算法 247
6.4.2 Shank算法 252
6.5 二項同餘方程與n次剩餘 254
6.6 原根與離散對數的套用 257
6.6.1 Diffie-Hellman密鑰交換算法 257
6.6.2 ElGamal加密算法 258
6.6.3 改進的隨機數生成算法 261
6.6.4 一種快速傅立葉變換算法 263
6.6.5 同餘方程的求解 264
6.7 單向函式 266
習題6 267
第 7 章 連分數 271
7.1 連分數 271
7.1.1 連分數的概念 271
7.1.2 連分數性質與漸進連分數的計算 274
7.2 簡單連分數 279
7.2.1 實數的簡單連分數的生成 279
7.2.2 有理分數的連分數表示 281
7.3 循環連分數 283
習題7 284
第 8 章 素性測試和整數分解 287
8.1 素性測試的精確方法 287
8.2 偽素數與Fermat測試算法 289
8.3 Euler偽素數與Solovay-Stassen測試算法 292
8.3.1 Euler偽素數 292
8.3.2 Solovay-Stassen測試算法 293
8.4 強偽素數與Miller-Rabin測試算法 293
8.4.1 強偽素數 295
8.4.2 Miller-Rabin測試算法 295
8.5 正整數的分解 297
8.5.1 Fermat方法 298
8.5.2 Fermat方法的拓展 299
8.5.3 Legendre方法 299
8.5.4 Pollard方法 300
8.5.5 Kraitchik方法 301
8.5.6 B基數法——Brillhart-Morrison法 303
8.5.7 連分數法 306
8.5.8 二次篩法 308
8.5.9 p-1法 310
習題8 312
第9章 有限域 314
9.1 集合及其運算 314
9.1.1 集合 314
9.1.2 映射 315
9.1.3 代數運算 317
9.1.4 同構映射 317
9.2 群 319
9.3 環 323
9.3.1 環 323
9.3.2 多項式環 325
9.4 域 329
9.4.1 域的概念 329
9.4.2 域的特徵和同構 332
9.4.3 有限域及其結構 335
9.4.4 有限域的構造 337
9.4.5 GF（2n）域上的計算 341
習題 9 343
附錄A 素數表與最小正原根表(1200以內) 345
附錄B k的連分數 346
附錄C F2上的既約多項式(n≤10) 348
附錄D F2上的本原多項式 350
索引 352
參考文獻 361
