An introduction to number theory with cryptography (Q2850606)

The second author, Professor of Mathematics and distinguished scholar-teacher at the University of Maryland, USA, is a renowned number theorist and textbook author, not least through his popular primers on cyclotomic fields, elliptic curves, and cryptography (with V. Trappe), respectively. The book under review, written with James S. Kraft as co-author, is another introductory text of his in number theory, and certainly both the most general and the most elementary one among these books.NEWLINENEWLINE NEWLINEAs the authors point out in the preface, the goal of this treatise is to present a selection of arithmetic topics that not only show the great fascination of number theory as one of the purest areas of pure mathematics, but also its increasing practical applications to modern subjects such as cryptography. According to this didactic strategy, the book could serve as a source for an undergraduate course in number theory, but it also be used in a course for advanced high school students, or as a companion for independent study likewise. However, and above all, the authors' main objective is to demonstrate that ``number theory is supposed to be fun''.NEWLINENEWLINE NEWLINEAs to the contents, the material is organized in eighteen chapters and an appendix providing supplementary topics. Each chapter is subdivided into several sections, where the last two sections briefly list again the respective chapter highlights for self-control, on the one hand, and present problems to solve on the other. These problems appear in different forms, namely as (1) exercises, (2) projects, and (3) computer explorations. Whereas the exercises are easier working problems, the projects are much more substantial in nature, developing ideas gradually and more extensively. The computer explorations are an invitation to computational experimentation, thereby introducing the reader to this more recent methodology in contemporary number theory. Finally, at the end of most sections, there are specific problems labelled ``Check your understanding'', which present a particular help for the unexperienced reader struggling with the single topics treated in the book.NEWLINENEWLINE NEWLINEWith regard to the latter, Chapter 0 gives a first introduction to the history of number theory via comments on Diophantine equations, modular arithmetic, prime numbers, and cryptography. Chapter 1 deals with the elementary properties of the integers, with the focus on the concepts of divisibility, prime numbers, linear Diophantine equations, Fermat and Mersenne numbers, the postage stamp problem, and on a first cryptographic application of the division algorithm. Chapter 2 explains the unique factorization property of integers and the Fundamental Theorem of Arithmetic, whereas Chapter 3 illustrates several instructive applications of unique factorization, including puzzle problems, irrationality proofs, Pythagorean triples, differences of squares, an introduction to the Riemann zeta function, and other elementary examples. Chapter 4 turns to linear congruences and the related classical theorems, while Chapter 5 is devoted to concrete cryptographic applications such as shift and affine ciphers, the general problem of secret sharing, and the RSA cryptosystem. Chapter 6 very briefly addresses polynomial congruences for later use, and Chapter 7 discusses in greater detail Fermat numbers, Mersenne numbers, primitive roots of unity, decimals and Midy's theorem, the famous ``discrete log problem'', and further instructive applications. More cryptographic applications are presented in Chapter 8 namely the Diffie-Hellman key exchange, the method of coin flipping over a telephone, mental poker, the El-Gamal public key cryptosystem, and the idea of digital signatures. All this is explained in a very comprehensible down-to-earth language, very much to the benefit of the novice in the field. The main topic of the subsequent Chapter 9 is the law of quadratic reciprocity. Thereafter, in Chapter 10, primality and factorization problems are dealt with including trial division and Fermat factorization, pseudoprimes and Carmichael numbers, primality tests, factoring using RSA exponents, Pollard's \(p-1\) factorization method, and the quadratic sieve due to C. Pomerance. Chapter 11 turns to the geometry of numbers, with the emphasis on Minkowski's convex body theorem and its applications to sums of two squares, sums of four squares, and Pell's equation. Chapter 12 touches upon multiplicative arithmetic functions and the concept of perfect numbers, before Chapter 13 develops the rudiments of the theory of continued fractions and their applications to the representation of square roots of integers as well as to the proofs of irrationality of the real numbers \(e\), \(\pi\) and \(\pi^2\). In the sequel, the ring of Gaussian integers is analyzed in Chapter 14 while Chapter 15 discusses further quadratic number fields, their rings of integers and the units therein, the Lucas-Lehmer primality test for Mersenne numbers as an application, and \(\mathbb Z[\sqrt{-5}]\) is an example of a non-factorial ring. Chapter 16 shows how analytic techniques from calculus can be used to obtain elementary results about the distribution of prime numbers, e.g., Bertrand's postulate and Chebyshev's approximate prime number theorem. Chapter 17, the last chapter of the main text, is an epilogue providing an outlook to Fermat's Last Theorem and its recent proof via curves and the modularity property.NEWLINENEWLINE NEWLINEAppendix A contains some supplementary, mostly elementary topics that are used in the course of the main text. Those are meant to make the book entirely self-contained. Appendix B provides answers or hints to the odd-numbered problems given at the and of each chapter.NEWLINENEWLINE NEWLINEAt the very beginning of the book, there is a diagram showing the interdependence of single chapters, but there is no bibliography with hints for further, more advanced reading. Nevertheless, the present book is anyway completely self-contained and serves its declared educational purpose as an invitation to number theory and its applications to cryptography perfectly well. The presentation of the material is utmost lucid, instructive and entertaining, which makes the book an excellent source for studious neophytes and devoted teachers likewise. Several topics beyond the standard ones covered in undergraduate classes lead the interested reader to problems in contemporary number theory and information theory, which certainly represents one of the most outstanding pedagogical features of the textbook under review.