數(shù)論是研究整數(shù)性質(zhì)的一個數(shù)學(xué)分支，它歷史悠久，有著強大的生命力。數(shù)論問題敘述簡明，“很多數(shù)論問題可以從經(jīng)驗中歸納出來，并且僅用三言兩語就能向一個行外人解釋清楚，但要證明它卻遠非易事”，因而有人說：“用以發(fā)現(xiàn)天才，在初等數(shù)學(xué)中再也沒有比數(shù)論更好的課程了”，所以在國內(nèi)外各級各類的數(shù)學(xué)競賽中，數(shù)論問題總是占有相當大的比重。
隨著科學(xué)技術(shù)的發(fā)展，將經(jīng)典理論與現(xiàn)代應(yīng)用相結(jié)合已成為發(fā)展的一種趨勢，故數(shù)論的應(yīng)用領(lǐng)域也逐漸擴展開來，順應(yīng)發(fā)展趨勢，推動數(shù)論應(yīng)用，正是本書的編寫目的和出發(fā)點。實際上，目前數(shù)論的有關(guān)理論和方法在計算機、通信等領(lǐng)域有著大量的應(yīng)用，尤其在信息和網(wǎng)絡(luò)安全、數(shù)字信號處理等方面應(yīng)用更加廣泛，而本書也主要從應(yīng)用角度出發(fā)來研究數(shù)論問題，尤其是有關(guān)整數(shù)運算中實用的方法和具體算法。
本書共分9章，各章的主要內(nèi)容概括如下：
第1章整數(shù)的可除性，主要介紹整除概念及與其相關(guān)的問題，如整除的定義及其性質(zhì)，重點介紹了求最大公因數(shù)的有關(guān)算法。
第2章數(shù)論函數(shù)，給出了幾種常用數(shù)論函數(shù)并討論了其性質(zhì)，同時介紹了函數(shù)的積性和函數(shù)的Dirichlet乘積等概念及性質(zhì)。
第3章同余及其運算，介紹了整數(shù)按同余的分類、同余條件下冪函數(shù)的快速運算算法，給出了不定方程的解法、矩陣的同余運算和同余在信息安全和隨機數(shù)生成方面的應(yīng)用實例。
第4章同余方程，介紹了同余方程的概念，討論了同余方程的解數(shù)及解法，給出了一次同余方程組和素數(shù)模的同余方程的求解方法及同余方程在秘密共享和數(shù)據(jù)加密方面的應(yīng)用實例。
第5章二次同余方程與平方剩余，主要針對特殊的同余方程（即二次同余方程的求解）給出了問題的分類、化簡和轉(zhuǎn)換方法，重點介紹了利用勒讓德符號和雅可比符號判斷方程的可解性和模數(shù)為素數(shù)時的求解方法。
第6章原根與離散對數(shù)，從整數(shù)的階與原根的定義出發(fā)，給出了階的性質(zhì)、原根及其判斷方法與計算方法、 n次剩余以及利用原根解特殊高次方程的方法，最后給出了原根和離散對數(shù)在密鑰管理、信息加密和隨機數(shù)生成等方面的應(yīng)用。
第7章連分數(shù)，介紹了連分數(shù)的概念和有關(guān)性質(zhì)，重點介紹了用連分數(shù)逼近實數(shù)和有理分數(shù)的方法。
第8章素性測試和整數(shù)分解，主要針對素數(shù)的精確判斷方法的復(fù)雜度問題，介紹了素數(shù)的概率測試，以及正整數(shù)的分解方法。
第9章有限域，主要討論與數(shù)論相關(guān)的群、環(huán)、域的概念和性質(zhì)，重點介紹了同余運算與群、環(huán)、域的關(guān)系，以及利用同余運算實現(xiàn)有限域的構(gòu)造等問題。
本書具有如下幾個特點：
(1) 緊密結(jié)合研究生教學(xué)實際和教學(xué)大綱，在內(nèi)容編排上力求深入淺出，循序漸進；在講解理論和原理的同時，給出了大量例題，并在講解例題時，重視對解題思路的分析，有利于提高讀者獨立分析問題和解決問題的能力。
(2) 針對工科研究生教學(xué)要求，書中除了數(shù)論的理論成果外，還結(jié)合實際應(yīng)用，搜集并整理了相關(guān)問題的實用算法，盡力做到與時俱進，重在實用。
(3) 注重教學(xué)思想方法的滲透和解題水平的提高。拾眾家之所長，精選題目，使例題和習(xí)題均具有典型性和代表性。
(4) 本書在撰寫時，參閱了國內(nèi)外大量的相關(guān)資料，并凝結(jié)了作者十多年來從事研究生“數(shù)論算法”課程教學(xué)的體會，力求內(nèi)容新穎，取舍得當。
本書是在西安電子科技大學(xué)校內(nèi)教材“數(shù)論算法”的基礎(chǔ)上，經(jīng)過多年的試用，并吸取了老師和學(xué)生大量的修改意見，不斷完善而成的。
西安電子科技大學(xué)出版社對本書的出版給予了熱情的關(guān)懷和支持，尤其是出版社李惠萍老師對書稿嚴格把關(guān)，在內(nèi)容的敘述方式上提出了很多有益的建議，使作者深受教益，在此表示感謝。
由于作者水平有限，書中不足之處在所難免，懇請讀者批評指正，使本書得以不斷改進和完善。
第 1 章 整數(shù)的可除性
1.1 整除的概念與帶余除法
1.1.1 整除及其性質(zhì)
1.1.2 素數(shù)
1.1.3 帶余除法
1.2 整數(shù)的表示
1.3 最大公因數(shù)與輾轉(zhuǎn)相除法
1.3.1 最大公因數(shù)
1.3.2 輾轉(zhuǎn)相除法
1.3.3 求（a，b）的算法
1.3.4 （a，b）與a、b的關(guān)系
1.3.5 其他性質(zhì)
1.4 整除的進一步性質(zhì)及最小公倍數(shù)
1.4.1 整除和最大公因數(shù)的其他性質(zhì)
1.4.2 最小公倍數(shù)及其性質(zhì) 第 1 章 整數(shù)的可除性
1.1 整除的概念與帶余除法
1.1.1 整除及其性質(zhì)
1.1.2 素數(shù)
1.1.3 帶余除法
1.2 整數(shù)的表示
1.3 最大公因數(shù)與輾轉(zhuǎn)相除法
1.3.1 最大公因數(shù)
1.3.2 輾轉(zhuǎn)相除法
1.3.3 求（a，b）的算法
1.3.4 （a，b）與a、b的關(guān)系
1.3.5 其他性質(zhì)
1.4 整除的進一步性質(zhì)及最小公倍數(shù)
1.4.1 整除和最大公因數(shù)的其他性質(zhì)
1.4.2 最小公倍數(shù)及其性質(zhì)
1.5 算術(shù)基本定理
習(xí)題1
第 2 章 數(shù)論函數(shù)
2.1 數(shù)論函數(shù)
2.2 函數(shù)?x?|、 |?x? 、 ［x］
2.2.1 下整數(shù)函數(shù)?x?|
2.2.2 上整數(shù)函數(shù)|?x?
2.2.3 四舍五入函數(shù)［x］
2.3 函數(shù)potpn
2.4 Euler函數(shù)φ(n)
2.5 墨比烏斯函數(shù)μ(n)
2.5.1 墨比烏斯函數(shù)
2.5.2 墨比烏斯反演公式
2.6 素數(shù)個數(shù)函數(shù)π(n)
2.7 數(shù)論函數(shù)的狄利克雷乘積
2.8 積性函數(shù)
2.8.1 積性函數(shù)的定義
2.8.2 積性函數(shù)的性質(zhì)
習(xí)題2
第 3 章 同余及其運算
3.1 同余的概念及基本性質(zhì)
3.2 剩余類及完全剩余系
3.2.1 剩余類和完全剩余系
3.2.2 剩余類的性質(zhì)
3.3 既約剩余系
3.3.1 既約剩余系
3.3.2 整數(shù)a模m的逆
3.4 歐拉定理和費馬小定理
3.4.1 歐拉定理
3.4.2 費馬小定理
3.5 模重復(fù)平方計算法
3.5.1 算法原理
3.5.2 模重復(fù)平方計算法
3.6 一次不定方程
3.6.1 二元一次（不定）方程
3.6.2 求特解的方法
3.6.3 s元一次不定方程
3.6.4 （s元）一次不定方程組
3.7 矩陣的同余運算
3.7.1 矩陣及其線性運算
3.7.2 矩陣乘法
3.7.3 可逆矩陣
3.8 同余的應(yīng)用
3.8.1 RSA公鑰密碼算法
3.8.2 背包公鑰密碼算法
3.8.3 希爾密碼算法
3.8.4 隨機數(shù)的Lehmer生成算法
3.8.5 隨機數(shù)的BBS生成算法
習(xí)題3
第 4 章 同余方程
4.1 基本概念
4.2 一次同余方程
4.3 中國剩余定理
4.4 高次同余方程的解數(shù)及解法
4.4.1 解數(shù)
4.4.2 特殊情形的解法
4.4.3 一般情形的解法
4.5 素數(shù)模的同余方程
4.5.1 同余方程的化簡
4.5.2 解數(shù)的判斷
4.6 同余方程的應(yīng)用
4.6.1 密鑰分存
4.6.2 數(shù)據(jù)庫加密方案
4.6.3 BBS流密碼算法
習(xí)題4
第 5 章 二次同余方程與平方剩余
5.1 一般二次同余方程
5.1.1 二次同余方程的化簡
5.1.2 平方剩余
5.2 模為奇素數(shù)的平方剩余與平方非剩余
5.2.1 平方剩余的判斷條件
5.2.2 平方剩余的個數(shù)
5.3 勒讓德符號
5.4 雅可比符號
5.5 模p平方根
5.6 模數(shù)為合數(shù)的情形
5.6.1 p為奇素數(shù)
5.6.2 p＝2
5.7 解同余方程小結(jié)
習(xí)題5
第 6 章 原根與離散對數(shù)
6.1 整數(shù)的階及其性質(zhì)
6.1.1 整數(shù)的階和原根
6.1.2 階的性質(zhì)與計算方法
6.2 原根的存在性與計算方法
6.3 離散對數(shù)
6.4 離散對數(shù)的計算
6.4.1 Pohlid-Hellman算法
6.4.2 Shank算法
6.5 二項同余方程與n次剩余
6.6 原根與離散對數(shù)的應(yīng)用
6.6.1 Diffie-Hellman密鑰交換算法
6.6.2 ElGamal加密算法
6.6.3 改進的隨機數(shù)生成算法
6.6.4 一種快速傅里葉變換算法
6.6.5 同余方程的求解
6.7 單向函數(shù)
習(xí)題6
第 7 章 連分數(shù)
7.1 連分數(shù)
7.1.1 連分數(shù)的概念
7.1.2 連分數(shù)性質(zhì)與漸進連分數(shù)的計算
7.2 簡單連分數(shù)
7.2.1 實數(shù)的簡單連分數(shù)的生成
7.2.2 有理分數(shù)的連分數(shù)表示
7.3 循環(huán)連分數(shù)
習(xí)題7
第 8 章 素性測試和整數(shù)分解
8.1 素性測試的精確方法
8.2 偽素數(shù)與Fermat測試算法
8.3 Euler偽素數(shù)與Solovay-Stassen測試算法
8.3.1 Euler偽素數(shù)
8.3.2 Solovay-Stassen測試算法
8.4 強偽素數(shù)與Miller-Rabin測試算法
8.4.1 強偽素數(shù)
8.4.2 Miller-Rabin測試算法
8.5 正整數(shù)的分解
8.5.1 Fermat方法
8.5.2 Fermat方法的拓展
8.5.3 Legendre方法
8.5.4 Pollard方法
8.5.5 Kraitchik方法
8.5.6 B基數(shù)法——Brillhart-Morrison法
8.5.7 連分數(shù)法
8.5.8 二次篩法
8.5.9 p-1法
習(xí)題8
第9章 有限域
9.1 集合及其運算
9.1.1 集合
9.1.2 映射
9.1.3 代數(shù)運算
9.1.4 同構(gòu)映射
9.2 群
9.3 環(huán)
9.3.1 環(huán)
9.3.2 多項式環(huán)
9.4 域
9.4.1 域的概念
9.4.2 域的特征和同構(gòu)
9.4.3 有限域及其結(jié)構(gòu)
9.4.4 有限域的構(gòu)造
9.4.5 GF（2n）域上的計算
習(xí)題 9
附錄A 素數(shù)表與最小正原根表(1200以內(nèi))
附錄B k的連分數(shù)
附錄C F2上的既約多項式(n≤10)
附錄D F2上的本原多項式
索引
參考文獻
書單推薦
