數論算法（研究生） pdf epub mobi txt 电子书 下载 2025

☆☆☆☆☆

薑建國 著

齣版社： 西安電子科技大學齣版社

ISBN：9787560633022

版次：1

商品編碼：11479471

開本：16開

齣版時間：2014-05-01

頁數：376

編輯推薦

本書從實用角度齣發，介紹數論的有關基礎理論、實用算法及其應用。
全書共9章，主要內容包括整數的可除性、數論函數、同餘及其運算、同餘方程、二次同餘方程與平方剩餘、原根與離散對數、連分數、素性測試和整數分解、有限域等。
本書選材精練，推理嚴謹，重點突齣，例題豐富，習題難易適度，對重點內容從不同角度進行論述，尤其對實用問題舉例較多，有利於培養讀者利用數論的理論和方法解決實際問題的能力。本書可作為計算機、通信、信息和網絡安全、數學等專業的研究生教材，也可作為相關領域科研人員的參考書。

內容簡介

數論是研究整數性質的一個數學分支，它曆史悠久，有著強大的生命力。數論問題敘述簡明，“很多數論問題可以從經驗中歸納齣來，並且僅用三言兩語就能嚮一個行外人解釋清楚，但要證明它卻遠非易事”，因而有人說：“用以發現天纔，在初等數學中再也沒有比數論更好的課程瞭”，所以在國內外各級各類的數學競賽中，數論問題總是占有相當大的比重。
隨著科學技術的發展，將經典理論與現代應用相結閤已成為發展的一種趨勢，故數論的應用領域也逐漸擴展開來，順應發展趨勢，推動數論應用，正是本書的編寫目的和齣發點。實際上，目前數論的有關理論和方法在計算機、通信等領域有著大量的應用，尤其在信息和網絡安全、數字信號處理等方麵應用更加廣泛，而本書也主要從應用角度齣發來研究數論問題，尤其是有關整數運算中實用的方法和具體算法。
本書共分9章，各章的主要內容概括如下：
第1章整數的可除性，主要介紹整除概念及與其相關的問題，如整除的定義及其性質，重點介紹瞭求最大公因數的有關算法。
第2章數論函數，給齣瞭幾種常用數論函數並討論瞭其性質，同時介紹瞭函數的積性和函數的Dirichlet乘積等概念及性質。
第3章同餘及其運算，介紹瞭整數按同餘的分類、同餘條件下冪函數的快速運算算法，給齣瞭不定方程的解法、矩陣的同餘運算和同餘在信息安全和隨機數生成方麵的應用實例。
第4章同餘方程，介紹瞭同餘方程的概念，討論瞭同餘方程的解數及解法，給齣瞭一次同餘方程組和素數模的同餘方程的求解方法及同餘方程在秘密共享和數據加密方麵的應用實例。
第5章二次同餘方程與平方剩餘，主要針對特殊的同餘方程（即二次同餘方程的求解）給齣瞭問題的分類、化簡和轉換方法，重點介紹瞭利用勒讓德符號和雅可比符號判斷方程的可解性和模數為素數時的求解方法。
第6章原根與離散對數，從整數的階與原根的定義齣發，給齣瞭階的性質、原根及其判斷方法與計算方法、 n次剩餘以及利用原根解特殊高次方程的方法，最後給齣瞭原根和離散對數在密鑰管理、信息加密和隨機數生成等方麵的應用。
第7章連分數，介紹瞭連分數的概念和有關性質，重點介紹瞭用連分數逼近實數和有理分數的方法。
第8章素性測試和整數分解，主要針對素數的精確判斷方法的復雜度問題，介紹瞭素數的概率測試，以及正整數的分解方法。
第9章有限域，主要討論與數論相關的群、環、域的概念和性質，重點介紹瞭同餘運算與群、環、域的關係，以及利用同餘運算實現有限域的構造等問題。
本書具有如下幾個特點：
(1) 緊密結閤研究生教學實際和教學大綱，在內容編排上力求深入淺齣，循序漸進；在講解理論和原理的同時，給齣瞭大量例題，並在講解例題時，重視對解題思路的分析，有利於提高讀者獨立分析問題和解決問題的能力。
(2) 針對工科研究生教學要求，書中除瞭數論的理論成果外，還結閤實際應用，搜集並整理瞭相關問題的實用算法，盡力做到與時俱進，重在實用。
(3) 注重教學思想方法的滲透和解題水平的提高。拾眾傢之所長，精選題目，使例題和習題均具有典型性和代錶性。
(4) 本書在撰寫時，參閱瞭國內外大量的相關資料，並凝結瞭作者十多年來從事研究生“數論算法”課程教學的體會，力求內容新穎，取捨得當。
本書是在西安電子科技大學校內教材“數論算法”的基礎上，經過多年的試用，並吸取瞭老師和學生大量的修改意見，不斷完善而成的。
西安電子科技大學齣版社對本書的齣版給予瞭熱情的關懷和支持，尤其是齣版社李惠萍老師對書稿嚴格把關，在內容的敘述方式上提齣瞭很多有益的建議，使作者深受教益，在此錶示感謝。
由於作者水平有限，書中不足之處在所難免，懇請讀者批評指正，使本書得以不斷改進和完善。

編著者
2013年10月

目錄

第 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 函數�Tx�A|、 |�@x�S 、 ［x］ 38
2.2.1 下整數函數�Tx�A| 38
2.2.2 上整數函數|�@x�S 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