數論與應用（簡體書）

《計算機系列教材：數論與應用》論述數論的基本內容。全書共分12章，內容包括整數的唯一分解定理、同餘運算、同余方程、二次同余方程與平方剩餘、不定方程、數論函數、指數和原根、素性判別、連分數與整數分解、代數數與超越數、密碼學和數論的應用。書中配有較多的例題和習題，書末附有提示與解答。
本書可作為信息安全、數論等專業的本科生教材，可供相關專業的研究人員、高等學校的教師參考，也可供數學工作者、中學數學教師和高中學生閱讀。

《普通高等教育"十一五"國家級規劃教材?計算機系列教材:數論與應用》可作為信息安全、數論等專業的本科生教材，可供相關專業的研究人員、高等學校的教師參考，也可供數學工作者、中學數學教師和高中學生閱讀。

第1章整數的唯一分解定理
1．1歸納定理
1．2整除、素數與合數
1．3帶餘數除法
1．4最大公因數與最小公倍數
1．5整數的唯一分解定理
1．6輾轉相除法
1．7素數定理
習題第2章同餘運算
2．1同餘
2．2剩餘類和完全剩餘系
2．3簡化剩餘系與Euler函數
2．4Euler定理與Fermat定理
2．5Wilson定理
2．6整數的剩餘表示
習題第3章同余方程
3．1同余方程和一次同余方程
3．2一次同余方程組和孫子定理
3．3高次同余方程
3．4模為高次冪的同余方程
3．5模為素數的同余方程
習題第4章二次同余方程與平方剩餘
4．1一般二次同余方程
4．2模為奇素數的二次同余方程
4．3勒讓德符號
4．4二次互反律
4．5雅可比符號
4．6模為奇素數的二次剩餘
4．7模為合數的二次剩餘
習題第5章不定方程
5．1二元一次不定方程
5．2?n?元一次不定方程
5．3方程?x?2+y?2=z?2?
5．4幾類特殊的不定方程
習題第6章數論函數
6．1函數［?x?］和{?x?}
6．2數論函數pot??p?(?u?)
6．3墨比烏斯函數
6．4數論函數的狄利克雷乘積
6．5積性函數
6．6歐拉函數
6．7?π(x)?的估值
習題第7章指數和原根
7．1指數
7．2原根及其存在的條件
7．3指標及?n?次剩餘
7．3．1指標的性質
7．3．2?n?次剩餘
習題第8章素性判別
8．1Fermat小定理
8．2擬素數和Fermat素性判別
8．3Euler擬素數與Solovay-StaSSen判別
8．4強擬素數與Miller-Rabin判別
8．5利用?n?-1的因子分解的素性判別
8．6利用?n?+1的因子分解的素性判別
8．7基於橢圓曲線的素性判別
習題第9章連分數與整數分解
9．1連分數的基本性質
9．2實數的連分數表示
9．3循環連分數
9．4連分數因子分解算法
9．5正整數的分解
9．5．1試除法
9．5．2Fermat方法
9．5．3Fermat方法的拓展
9．5．4勒讓德方法
9．5．5Kraitchik方法(19世紀20年代)
9．5．6B基數法：Brillhart-Morrison法
習題第10章代數數與超越數
10．1代數數
10．2二次代數數
10．3超越數
10．4數e的超越性
10．5數π的超越性
習題1第11章密碼學
11．1仿射加密方法
11．2RSA公鑰密碼
11．3Diffie-Hellman體制
11．4ElGamal加密算法
11．5背包型加密方法
11．6秘密共享
習題1第12章數論的應用
12．1計算星期幾
12．2循環比賽
12．3Nim遊戲
12．4散列函數
12．5校驗位
12．6孫子定理的應用
12．6．1文件集合的加密
12．6．2秘密共享
12．7原根的一個應用
習題1習題參考答案
參考文獻

一般來說，從密文求明文，有許多可能的方法，例如：
（1）將咒分解因數，求出p和q，使得n=pq，然后計算ψ（n）=（p—1）（q—1），利用輾轉相除法求出d，使得式（11—5）成立。再利用式（11—7）從密文E計算明文P。容易看出，用這種方法從密文求出明文的難度，就是將大整數分解因數的難度。
（2）如果能用某種方法（不是先將n分解因數）求出ψ（n），則也可以從密文E求出明文P。因為，利用輾轉相除法，由e可以求出d使得式（11—5）成立，于是，由式（11—7）可以從密文E計算明文P。但是，如果ψ（n）=（p—1）（q—1）是已知的，那么，有pq=n以及由此，可以利用二元一次方程組求出P和q。這說明，這種方法的難度不會低于將大整數分解因數的難度。
例11—4 下面舉例說明RSA密碼系統的加密過程。假設加密模數是素數43和59的乘積（這比實際應用的大素數小得多），這樣得到以n=43×9—2537為模，取e=13作為次數，易知（e，ψ（n））=（13，42×58）=1。然后加密下面信息
PUBLIC KEY CRYPTOCRAP HY
解首先將字母轉為對應的數值，將這些數字分為長度為4的數據組。注意，這里字母與數字的對應關系為A～Z對應00～25。可以得到
1520 0111 0802 1004
2402 1724 1519 1406
1700 1507 2423
其中添加了空字母X=23以填滿最后的數據組。
利用下述關系式，將每一明文數據組加密為密文數據組
E=P13（rood 2537）
即可得到密文信息
0095 1648 1410 1299
0811 2333 2132 0370
1185 1957 1084
要解密用RSA密碼加密的信息，必須找到e=13模ψ（2537）=2426的逆，然后利用式（11—7）即可。
除此之外，還有一些別的方法。對于這些方法的分析，有興趣的讀者可以查閱關于密碼學的文獻。總的來說，RSA加密方法被認為有較好的安全性。
RSA加密方法的特點，在于加密方法是公開的，而且加密時所使用的參數也是公開的。這是它與仿射加密方法的重要區別。通常，稱具有這種特點的加密方法為公鑰加密方法。公鑰加密方法使得信息的加密傳送更為方便。例如，每個單位或個人可以像公布電話號碼一樣公布自己的RSA加密鑰。于是，凡是要向它或他發送加密信息的單位或個人都可以使用這些參數發送加密信息。此外，RSA加密方法還有更廣泛的用途。
RSA加密方法可以用來進行簽證，不需要當事人到場，只需要傳送必要的信息。
在社會生活中，在處理具體事件時，常需要當事人進行簽證（簽名），以保證他做出的許諾或送出的信息的可靠性與合法性。例如，在簽署文件時，由當事人簽名，蓋章，簽署日期以及重要的特殊記號，常是不可少的環節。這樣的簽證，應該滿足一定的要求。
假設A簽證一個文件給B，那么，
（1）B應該能夠確定這是否A的簽證。
（2）任何其他人，無法偽造A的簽證，即A有其獨特的簽證方式。
（3）有一個仲裁簽證是否由A發出的方法，例如，當A否認這個簽證時，這樣的方法可以鑒定簽證的真偽。