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"问题，借助书末答案做奇数编号练习，并用计算机代数系统完成因数分解和素性检验的计算机探究。