初等数论及其应用（英文版· 原书第7版）

本书是为大学本科的数论课程而写的，适用于任何水平，除了一定的数学素养外，本书的大部分材料不需要什么预备知识，本书既可以作为计算机科学课程的有益补充，也可以作为有兴趣学习数论和密码学新进展的读者的初级读物，第7版保持了先前版本的长处，并加以充实、改进，熟悉先前版本的教师将会乐于使用这个新版本，初次使用本书的教师则会看到这样一本新的教材，其中将跨越几千年的数论精华与新近不到十年的新进展加以整合，熟悉先前版本的教师将会发现新版本变得更灵活且更易于教学，也更加有趣和引人人胜，他们还将发现对于数论成果的历史渊源及数论的实验方面的额外关注。

肯尼思·H.罗森（Kenneth H.Rosen）密歇根大学安娜堡分校数学学士，麻省理工学院数学博士。他曾就职于科罗拉多大学、俄亥俄州立大学、缅因大学和蒙茅斯大学，教授离散数学、算法设计和计算机安全方面的课程；他还曾加盟贝尔实验室，并且是 AT&T 贝尔实验室的杰出技术人员。<br /><br />他的著作《初等数论及其应用》和《离散数学及其应用》均被翻译成多种语言，在全球数百所大学中广为采用。

目　　录<br />何谓数论　1<br />第1章　整数　5<br />1.1　数和序列　5<br />1.2　和与积　17<br />1.3　数学归纳法　24<br />1.4　斐波那契数　31<br />1.5　整除性　39<br />第2章　整数的表示法和运算　47<br />2.1　整数的表示法　47<br />2.2　整数的计算机运算　57<br />2.3　整数运算的复杂度　64<br />第3章　最大公因子　71<br />3.1　最大公因子及其性质　71<br />3.2　欧几里得算法　80<br />3.3　线性丢番图方程　90<br />第4章　素数　99<br />4.1　素数概述　99<br />4.2　素数的分布　111<br />4.3　算术基本定理　129<br />4.4　因子分解方法和费马数　144<br />第5章　同余　155<br />5.1　同余概述　155<br />5.2　线性同余方程　168<br />5.3　中国剩余定理　173<br />5.4　求解多项式同余方程　182<br />5.5　线性同余方程组　189<br />5.6　利用波拉德ρ方法分解整数　198<br />第6章　同余的应用　203<br />6.1　整除性检验　203<br />6.2　万年历　209<br />6.3　循环赛赛程　214<br />6.4　散列函数　216<br />6.5　校验位　220<br />第7章　特殊的同余式　229<br />7.1　威尔逊定理和费马小定理　229<br />7.2　伪素数　238<br />7.3　欧拉定理　248<br />第8章　算术函数　253<br />8.1　欧拉φ函数　253<br />8.2　因子和与因子个数　265<br />8.3　完全数和梅森素数　271<br />8.4　莫比乌斯反演　288<br />8.5　拆分　296<br />第9章　密码学　313<br />9.1　字符密码　313<br />9.2　分组密码和流密码　322<br />9.3　指数密码　340<br />9.4　公钥密码学　343<br />9.5　密码协议及应用　353<br />第10章　原根　365<br />10.1　整数的阶和原根　365<br />10.2　素数的原根　373<br />10.3　原根的存在性　379<br />10.4　离散对数和指数的算术　388<br />10.5　用整数的阶和原根进行<br />　素性检验　400<br />10.6　通用指数　407<br />第11章　整数的阶的应用　413<br />11.1　伪随机数　413<br />11.2　埃尔伽莫密码系统　423<br />11.3　电话线缆绞接中的一个应用　429<br />第12章　二次剩余　437<br />12.1　二次剩余与二次非剩余　438<br />12.2　二次互反律　454<br />12.3　雅可比符号　466<br />12.4　欧拉伪素数　476<br />12.5　零知识证明　485<br />第13章　十进制分数与连分数　493<br />13.1　十进制分数　493<br />13.2　有限连分数　506<br />13.3　无限连分数　515<br />13.4　循环连分数　528<br />13.5　用连分数进行因子分解　543<br />第14章　非线性丢番图方程与<br />　椭圆曲线　547<br />14.1　毕达哥拉斯三元组　548<br />14.2　费马大定理　556<br />14.3　平方和　572<br />14.4　佩尔方程　584<br />14.5　同余数和椭圆曲线　591<br />14.6　模素数椭圆曲线　608<br />14.7　椭圆曲线的应用　617<br />第15章　高斯整数　625<br />15.1　高斯整数和高斯素数　625<br />15.2　最大公因子和唯一因子分解　636<br />15.3　高斯整数与平方和　647<br />附录A　整数集公理　653<br />附录B　二项式系数　657<br />附录C　Maple、Mathematica和SageMath<br />　在数论中的应用　665<br />C.1　Maple在数论中的应用　665<br />C.2　Mathematica在数论中的应用　670<br />C.3　SageMath在数论中的应用　677<br />附录D　有关数论的网站　683<br />附录E　表　685<br />附录F　未解决问题精选　701<br />参考文献　705<br /><br /><br />Contents<br /><br />What Is Number Theory? 1<br />1The Integers 5<br />1.1Numbers and Sequences 5<br />1.2Sums and Products 17<br />1.3Mathematical Induction 24<br />1.4The Fibonacci Numbers 31<br />1.5Divisibility 39<br />2Integer Representations and Operations<br />2.1Representations of Integers 47<br />2.2Computer Operations with Integers 57<br />2.3Complexity of Integer Operations 64<br />3Greatest Common Divisors 71<br />3.1Greatest Common Divisors and Their Properties 71<br />3.2The Euclidean Algorithm 80<br />3.3Linear Diophantine Equations 90<br />4Prime Numbers 99<br />4.1Prime Numbers 99<br />4.2The Distribution of Primes 111<br />4.3The Fundamental Theorem of Arithmetic 129<br />4.4Factorization Methods and the Fermat Numbers 144<br />5Congruences 155<br />5.1Introduction to Congruences 155<br />5.2Linear Congruences 168 <br />5.3The Chinese Remainder Theorem 173<br />5.4Polynomial Congruences 182<br />5.5Systems of Linear Congruences 189<br />5.6Factoring Using the Pollard Rho Method 198<br />6Applications of Congruences 203<br />6.1Divisibility Tests 203<br />6.2The Perpetual Calendar 209<br />6.3Round-Robin Tournaments 214<br />6.4Hashing Functions 216<br />6.5Check Digits 220<br />7Some Special Congruences 229<br />7.1Wilson‘s Theorem and Fermat’s Little Theorem 229 <br />7.2Pseudoprimes 238 <br />7.3Euler’s Theorem 248<br />8Arithmetic Functions 253<br />8.1The Euler Phi-Function 253<br />8.2The Sum and Number of Divisors 265<br />8.3Perfect Numbers and Mersenne Primes 271<br />8.4Mobius Inversion 288<br />8.5Partitions 296<br />9Cryptology 313<br />9.1Character Ciphers 313<br />9.2Block and Stream Ciphers 322<br />9.3Exponentiation Ciphers 340<br />9.4Public Key Cryptography 343<br />9.5Cryptographic Protocols and Applications 353<br />10Primitive Roots 365<br />10.1The Order of an Integer and Primitive Roots 365<br />10.2Primitive Roots for Primes 373<br />10.3The Existence of Primitive Roots 379<br />10.4Discrete Logarithms and Index Arithmetic 388 <br />10.5Primality Tests Using Orders of Integers and Primitive Roots 400<br />10.6Universal Exponents 407<br />11Applications of the Order of an Integer 413<br />11.1Pseudorandom Numbers 413<br />11.2The ElGamal Cryptosystem 423<br />11.3An Application to the Splicing of Telephone Cables 429<br />12Quadratic Residues 437<br />12.1Quadratic Residues and Nonresidues 438<br />12.2The Law of Quadratic Reciprocity 454<br />12.3The Jacobi Symbol 466<br />12.4Euler Pseudoprimes 476<br />12.5Zero-Knowledge Proofs 485<br />13Decimal Fractions and Continued Fractions<br />13.1Decimal Fractions 493<br />13.2Finite Continued Fractions 506<br />13.3Infinite Continued Fractions 515<br />13.4Periodic Continued Fractions 528<br />13.5Factoring Using Continued Fractions 543<br />14Nonlinear Diophantine Equations and Elliptic Curves 547<br />14.1Pythagorean Triples 548<br />14.2Fermat’s Last Theorem 556<br />14.3Sums of Squares 572<br />14.4Pell’s Equation 584<br />14.5Congruent Numbers and Elliptic Curves 591<br />14.6Elliptic Curves Modulo Primes 608<br />14.7Applications of Elliptic Curves 617<br />15The Gaussian Integers 625<br />15.1Gaussian Integers and Gaussian Primes 625<br />15.2Greatest Common Divisors and Unique Factorization 636<br />15.3Gaussian Integers and Sums of Squares 647?<br />Appendix AAxioms for the Set of Integers 653<br />Appendix BBinomial Coefficients 657<br />Appendix CUsing Maple, Mathe-matica, and SageMath for Number Theory 665<br />C.1Using Maple for Number Theory 665 <br />C.2Using Mathematica for Number Theory 670 <br />C.3Using SageMath for Number Theory 677<br />Appendix DNumber Theory Web Links 683<br />Appendix ETables 685<br />Appendix FInventory of Unsolved Problems 701 <br />Bibliography 705<br />