Browse Books

Reviewer: S. Nagaraj

Algebra and number theory are important subdisciplines of mathematics. They play an essential role in modern computer science, as evidenced by applications such as coding theory and cryptography. Consequently, books that introduce the computational aspects of number theory and algebra will help novices appreciate such applications. This introductory book is a revised second edition of a book that first appeared in 2005. It underscores algorithms and applications, and is intended for a wide audience. The presentation switches between theory and applications. The book covers the basics of number theory, abstract algebra, and discrete probability theory. It includes a total of 650 exercises and 280 worked examples. Compared to the previous edition, this one incorporates 150 new exercises. The material has been reorganized to improve clarity. Prerequisites are kept to a bare minimum-undergraduate mathematics and some familiarity with programming, algorithm analysis, and discrete mathematics. An electronic version of the book is available from Shoup's Web site [1]. Topics covered in the book include: basic properties of integers; congruences; computing with large integers; Euclid's algorithm; the distribution of primes; Abelian groups; rings; finite and discrete probability distributions; probabilistic algorithms; probabilistic primality testing; finding generators and discrete logarithms; quadratic reciprocity and computing modular square roots; modules and vector spaces; matrices; subexponential-time discrete logarithms and factoring; more rings; polynomial arithmetic and applications; linearly generated sequences and applications; finite fields; algorithms for finite fields; and deterministic primality testing. An appendix lists some useful facts. The number of pages in the new edition has gone up by about 60 pages. Two chapters in the first edition-the one on quadratic residues and quadratic reciprocity, and the one on computational problems related to quadratic residues-have been merged into a single chapter in the second edition, "Quadratic Reciprocity and Computing Modular Square Roots," reducing the number of chapters by one. Topics logically related, such as the chapters on probabilistic algorithms and probabilistic primality testing, have been brought together. A few chapters, such as those on Abelian groups and rings, are introduced earlier than before. The titles of the chapters are essentially the same in the two editions, but the contents have undergone change-some topics were added, while some were deleted or modified. One of the chapters whose size increased considerably is the one on congruences. One of the chapters that was reduced is, surprisingly, the chapter on probabilistic primality testing. Topics whose exclusion from the book is notable include the theory of lattices, along with algorithms for and applications of lattice basis reduction. This is rather surprising, considering that lattice basis reduction plays a significant role in computational number theory, algebra, and cryptography. It is all the more unexpected, since Shoup has developed a software package that includes routines for lattice basis reduction. The exclusion of these topics is highly unfortunate and I hope that they will be included in future editions of the book. The second edition corrects some errors in the first edition and includes new examples. The number of citations to the literature has increased marginally, by just six-from 105 to 111; the author should have provided a more substantial number of references to add value to the book. Despite the reorganization of the material, the inclusion of additional exercises and examples, and the increase in the size of the book by about ten percent, a second edition is hardly justified. The author could have included some thought-provoking exercises, programming challenges, open problems, and additional references, and emphasized the implementation of algorithms. Despite these shortcomings, the book will continue to serve as a good textbook for introductory courses in algebra and number theory, especially for students of computer science. Online Computing Reviews Service

Reviewer: Alasdair McAndrew

It's a pleasure to find a book that is so masterful and so well written that it has all the hallmarks of a classic. This is such a book. Shoup set himself the difficult task of bringing readers up to speed with number theory and algebra, starting "from scratch" (he is quite successful). My main complaint is that the book is not longer, but as Shoup regretfully observes in the introduction, some important topics were omitted to keep the book a reasonable size. Many books on computational number theory present the theory as a sort of smorgasbord of algorithms: primality testing, factorization, discrete logarithms, modular square, and n th roots. Shoup steers clear of this recipe approach and, instead, places the entire theory into a formal algebraic setting. This allows not only for elegance of exposition and remarkable clarity, but also provides the entire book with structural homogeneity. Even though "some topics could simply not be covered," it manages to include a wide range of topics. The book is geared toward students of cryptography and coding theory, as it covers the most relevant material in those disciplines. The book starts with several standard integer-based number theory concepts: divisibility; congruences and modular arithmetic, including quadratic residues (but reciprocity is treated later); large integer arithmetic; Euclid's algorithm and its association with the Chinese remainder theorem; and a brief discussion of the RSA cryptosystem, including a particularly elegant proof of its correctness. All of this material is standard for many other texts, yet it is rarely treated with as much care as here, in spite of the relative brevity. The first few chapters contain as much mathematics as many other entire cryptography texts and yet, at this stage, we are not even one fifth into the book. Another chapter discusses the distribution of primes, including a proof of Bertrand's postulate and a discussion of the prime number theorem. Given the importance of primes to modern cryptography, these are vital topics, so it is refreshing to see them treated so carefully. These first chapters set the scene, so to speak, for the number theory with which the text is concerned. However, much of the subsequent material is discussed in terms of the general theory of groups and rings. Primitive roots, for example, are not discussed as such, but in terms of generators of the nonzero residues of integers modulo a prime. Although this approach might seem at first to be unnecessarily obtuse, it is in fact the most natural way to introduce these algorithms, as it places them squarely in a generalized algebraic theory. The text, as one would expect, contains several chapters that discuss the basic theory of abelian groups and rings, including a fine proof of the fundamental theorem of the structure of finite abelian groups as sums of cyclic groups. What makes this book unique is the way in which several different mathematical strands?number theory and algebra?are interwoven and made into a masterful whole. Apart from rings and fields, there is much linear algebra (modules, vector spaces, and matrices), as well as a considerable amount of probability distributions and probabilistic algorithms, culminating in the Miller-Rabin test for primality and a few applications. The book ends with some chapters on finite fields and their various algorithms and a chapter on the Agrawal-Kayal-Saxena (AKS) deterministic primality test; the author carefully observes that the probabilistic Miller-Rabin test is much faster than AKS and, hence, should be preferred for all practical purposes. Nonetheless, as an ingenious use of much number theory and algebra, the AKS algorithm is a lovely example with which to finish the text. Although the text does not require much specific mathematical background, I would hesitate to use it except in an advanced class, or with students whose mathematical ability is already high. The material moves swiftly¿while never compromising rigor¿and the multiple strands assume considerable ability on the part of the reader. I was pleased to see copious exercises; a student who has completed the book and mastered the exercises will be in a very strong position to embark on some advanced studies. The author does not recommend any specific chapter sequence for a semester's study, but an astute teacher could pull some parts from this text for an initial course of study, and then complete the text in an advanced course. One regrettable omission is computational tools¿neither Shoup's own C++ NTL library for computational number theory and algebra nor a computer algebra system. A companion volume, or some material on the author's Web site that discusses some implementation issues, would be most welcome. (Note: the entire text is available under a Creative Commons license on the author's Web site (http://www.shoup.net/). This is a truly magnificent text, deserving of a place on the shelves of any mathematician or computer scientist working in these areas. Online Computing Reviews Service