01 / 導讀
導讀
引用
Kraft, J. S., & Washington, L. C. (2018). An Introduction to Number Theory with Cryptography (2nd ed.). Chapman & Hall/CRC.
章節概要
全書共21章和兩個附錄。每章以章節要點（Chapter Highlights）和習題部分結束，習題部分分為練習、專案、計算機探究和"Check Your Understanding"（理解檢測）問題的答案，不過並非每一章四個部分都齊全。出版社介紹說，第2版把一些RSA之前的基礎密碼學內容移到了更靠前的章節，使密碼學可以緊接在同餘之後講授。
第1章：引言
預告本書的四個主題：丟番圖方程、模算術、質數及其分佈，以及密碼學。
第2章：整除性
從整除性、關於質數有無窮多個的歐幾里得定理和歐幾里得的原始證明講起，然後是埃拉托斯特尼篩法和帶餘除法（附一個密碼學應用）。接著講最大公約數、歐幾里得演算法及其擴充套件形式、其他進位制，以及費馬數和梅森數。
第3–4章：線性丟番圖方程；唯一分解
第3章求解 ax + by = c，並討論郵票問題。第4章從分解的出發點講起，證明算術基本定理，並討論歐幾里得是如何處理它的。
第5章：唯一分解的應用
用唯一分解推出一系列結果：無理性證明（包括2的平方根為無理數的另外四個證明）、有理根定理、勾股數、平方差、階乘的質因數分解，以及黎曼ζ函數，其中包括質數倒數之和 1/p 發散。
第6章：同餘
定義與例子、模冪運算、整除判別法、線性同餘、中國餘數定理、模 m 的分數，以及在棋盤上擺放皇后的問題。
第7章：古典密碼系統
第一個密碼學章節：移位密碼與仿射密碼、維吉尼亞密碼、置換密碼、流密碼（一次性密碼本和線性反饋移位暫存器）、分組密碼、秘密共享，以及隨機數的生成。
第8章：費馬、歐拉與威爾遜
三個經典定理，各佔一節，是RSA和原根所依賴的經典結果。
第9章：RSA
RSA加密與數字簽名。
第10章：多項式同餘
質數模的多項式、質數冪模的解，以及合數模的情形。
第11章：階與原根
元質的階（包括費馬數和梅森數）、原根、小數（包括米迪定理）、洗牌、離散對數問題（大步小步法與指數演算法），以及原根存在性的證明。
第12章：更多密碼學應用
迪菲–赫爾曼金鑰交換、電話拋硬幣、心理撲克和ElGamal公鑰密碼系統。
第13章：二次互反律
質數模下的平方數與平方根、模 p 平方根的計算、二次方程、雅可比符號，以及二次互反律的證明。
第14章：質數檢定與因數分解
從試除法和費馬分解法開始，接著是質數檢定（偽質數、波克林頓–萊默檢驗、AKS檢驗，以及針對費馬數和梅森數的檢驗）和因數分解（x² ≡ y²、利用RSA指數分解、波拉德 p − 1 方法、二次篩法），最後回到電話拋硬幣。
第15–17章：數的幾何；數論函數；連分數
第15章講閔可夫斯基定理、兩個及四個平方數之和和佩爾方程，包括婆什迦羅的輪換法。第16章討論完全數和積性函數。第17章展開連分數，從有理逼近到週期展開、整數的平方根，再到若干無理數。
第18–19章：高斯整數；代數整數
第18章建立複數運算、高斯不可約元、帶餘除法和唯一分解，並應用於兩個平方數之和、勾股數和 y² = x³ − 1。第19章轉向二次域與代數整數、單位、環 Z[√−2] 和 Z[√3]（含盧卡斯–萊默檢驗），以及非唯一分解。
第20–21章：質數的分佈；尾聲：費馬大定理
第20章講伯特蘭假設和切比雪夫的近似質數定理。第21章是關於費馬大定理的尾聲，介紹橢圓曲線和模性。
附錄
附錄A"補充專題"：什麼是證明（含反證法）、等比級數、數學歸納法、帕斯卡三角形與二項式定理、斐波那契數和矩陣。附錄B給出奇數編號練習的答案與提示。
核心概念
第1–6章：基礎
- 歐幾里得演算法：計算最大公約數的方法，其擴充套件形式給出解丟番圖方程和求模逆元所需的係數。
- 唯一分解：每個整數在本質上以唯一的方式表為質數之積，是第5章各項應用的基礎。
- 同餘與中國餘數定理：模 m 的算術，以及模數不同的同餘式的組合。
第7–9章與第12章：密碼學
- 古典密碼：移位、仿射、維吉尼亞、置換、流和分組密碼，以及秘密共享和隨機數生成。
- RSA：建立在歐拉定理之上的公鑰加密與數字簽名。
- 迪菲–赫爾曼與ElGamal：基於離散對數問題的金鑰交換和公鑰加密。
第10–14章：根、互反律、質數檢定
- 原根與離散對數問題：其冪遍歷模 p 全部可逆元的元素，以及由冪求指數的問題。
- 二次互反律與雅可比符號：判斷一個數是否為質數模或合數模下的平方數。
- 偽質數與AKS檢驗：通過費馬型檢驗的合數，以及多項式時間的質數檢定。
第15–21章：進一步的專題
- 閔可夫斯基定理：證明平方和結果的一種幾何工具。
- 連分數與佩爾方程：有理逼近和一個經典的丟番圖方程。
- 高斯整數與代數整數：由複數或代數數構成的環，其中研究因數分解，包括分解不唯一的情形。
評析
優點
- 密碼學是融入而非附加。 密碼學出現在第1、7、9、12和14章，與它所用到的理論交織在一起：古典密碼在同餘之後，RSA在歐拉定理之後，離散對數在原根之後，因數分解方法在質數檢定一章。出版社強調這一版增加了密碼學的內容。
- 大量練習材料。 出版社稱練習、專案和計算機探究合計超過800道，另有可即時反饋的"Check Your Understanding"問題，以及奇數編號習題的答案與提示。每章的習題分為練習、專案和計算機探究。
- 對初學者的照顧。 關於什麼是證明、歸納法、等比級數、二項式定理和矩陣的附錄，把所需的預備知識集中在一處。出版社稱本書對優秀的高中生也易於理解、適合自學；S. V. Nagaraj 對初版的書評（2014年，由IACR託管）稱其文筆流暢、可讀性很強，補充材料對自學很有幫助。
- 有超出標準課程的空間。 數的幾何、高斯整數與代數整數、質數的分佈，以及關於費馬大定理的尾聲，為教師在核心內容之後提供了選擇；出版社也說書中包含少數較深入的專題，供想超越傳統課程的學生探索。
局限
- 超出一個學期。 約600頁（出版社給出的數字）、21章的篇幅無法在一個學期內講完，教師和自學者都需要取捨。
- 密碼學範圍有限。 書中的密碼學是數論式的：各種密碼、RSA、基於離散對數的體制、金鑰交換、拋硬幣和心理撲克。橢圓曲線只出現在費馬大定理的尾聲中，想學橢圓曲線密碼或協議安全性的讀者需要另找一本書。
- 尾聲是概覽。 第21章有三節（引言、橢圓曲線、模性），講解費馬大定理證明周圍的思想，但並不加以證明。
- 只有奇數編號練習有答案。 其餘練習的答案書中沒有給出，這對自學是個不便。
- 結尾處難度上升。 關於高斯整數和代數整數的第18–19章引入單位和非唯一分解等環論觀念，沒有接觸過抽象代數的學生可能會覺得上了一個臺階。
在課程中的定位
在本站的數論書籍中，Kraft 和 Washington 是把古典數論與現代密碼學放在一起講的一本。Burton 的 Elementary Number Theory 是最接近的古典替代選擇：它沿著相似的路線講到二次互反律，並配有關於相關數學家的歷史小節，在兩者之間選擇，主要看是偏好那條歷史線索，還是偏好密碼學和計算方面的應用。對剛接觸證明的讀者，Silverman 的 A Friendly Introduction to Number Theory 是以實驗和猜想為基礎的更平緩的入門，Robin Wilson 的 Number Theory: A Very Short Introduction 則是一本也談到公鑰密碼的緊湊概覽。
要進一步深入，Hardy 和 Wright 的 An Introduction to the Theory of Numbers 是初等數論與解析數論的經典論著，Ireland 和 Rosen 的 A Classical Introduction to Modern Number Theory 是以抽象代數為前提的研究生教材。Kraft 和 Washington 的最後幾章（高斯整數、代數整數、質數的分佈）是通向這兩本書的橋梁。
如何使用本書
出版社把本書設計給本科二至四年級的學生，並說它對優秀的高中生也易於理解，適合自學。本站列出的先修條件是一些證明經驗和基礎代數。附錄A為需要複習的讀者講解什麼是證明、歸納法和二項式定理。
一個實用的計畫如下：
- 數論核心： 第2–6章（整除性、線性丟番圖方程、唯一分解、同餘），然後是第8、11、13章（費馬、歐拉與威爾遜；原根；二次互反律）。
- 密碼學路線： 第7章緊接第6章之後，第9章的RSA在第8章之後，第12章和第14章放在它們所依賴的原根和互反律內容之後。
- 可選： 講多項式同餘的第10章，講數的幾何、數論函數和連分數的第15–17章，以及代數與解析拓展的第18–21章。
- 練習： 閱讀時使用"Check Your Understanding"問題，藉助書末答案做奇數編號練習，並用計算機代數系統完成因數分解和質數檢定的計算機探究。