# A Computational Introduction to Number Theory and Algebra

Victor Shoup, New York University

Copyright Year: 2009

Publisher: Cambridge University Press

Language: English

## Read this book

## Conditions of Use

Attribution-NonCommercial-NoDerivs

CC BY-NC-ND

## Reviews

This text is an introduction to number theory and abstract algebra; based on its presentation, it appears appropriate for students coming from computer science. The book starts with basic properties of integers (e.g., divisibility, unique... read more

This text is an introduction to number theory and abstract algebra; based on its presentation, it appears appropriate for students coming from computer science. The book starts with basic properties of integers (e.g., divisibility, unique factorization), and touches on topics in elementary number theory (e.g., arithmetic modulo n, the distribution of primes, discrete logarithms, primality testing, quadratic reciprocity) and abstract algebra (e.g., groups, rings, ideals, modules, fields and vector spaces, some linear algebra, polynomial rings and their quotients). The book also includes an introduction to probability. This, and other topics, are tools for interesting computational applications. The Table of Contents indicates a few sections that are not required for future material. The text includes an effective index.

From my research in writing this review, I have not come across any major errors. The author has a list of errata on his webpage.

The book appears to be up-to-date, and includes some interesting applications of theoretical material to topics relevant in cryptography (e.g., the RSA cryptosystem, and primality testing).

The presentation of topics is accurate, and starts "from scratch." All material necessary in future sections is included in the appropriate section. Some sections are terse, and an instructor may want to supplement the theoretical exercises with some more computational ones. The Euclidean Algorithm is presented after sections on solving linear congruences modulo n, and the Chinese Remainder Theorem; applications of the Euclidean Algorithm to these topics are presented later. An instructor may want students to become comfortable with these topics initially through computations, using the Euclidean Algorithm. We should also point out that mathematical induction is a prerequisite for this text, and some of the material is presented using pseudocode, which is different than many texts on these topics.

The book's terminology and mathematical frameworks appear to be consistent.

Since the book is quite long, an instructor for a one-semester course would need to choose specific topics from the text to cover. There are a few sections indicated that are not required for future material. However, even among the remaining sections, an instructor would need to carefully choose sections that include all necessary prerequisite material. Depending on a course's focus, this could be done fairly easily.

Each chapter is written in a logical manner, referencing previous material as needed. The book jumps from chapters on purely algebraic topics to those focused on applications. For this reason, an instructor may want to choose certain sections in a chapter to cover as prerequisites for an application, instead of covering the material linearly.

There do not appear to be any problems with the interface of the PDF of the text.

There do not appear to be major grammatical errors in the text.

Due to the topics in this text, this question does not appear to be applicable.

As promised by the title, the book gives a very nice overview of a side range of topics in number theory and algebra (primarily the former, but with quite a bit of attention to the latter as well), with special emphasis to the areas in which... read more

As promised by the title, the book gives a very nice overview of a side range of topics in number theory and algebra (primarily the former, but with quite a bit of attention to the latter as well), with special emphasis to the areas in which computational techniques have proved useful. There is a very good index and glossary and a good review of notation and basic facts in the first chapter.

The content is very accurate ad up to date. I see no signs of bias.

The format of the book makes it especially easy to update as advances in the subjects occur, particularly computational advances. References are given to websites as well as books.

The prose is very lucid and easy to follow. Many examples are given and difficult ideas are introduced gradually. The many relationships between number theory and algebra are explored in detail, each subject yielding important insights into and applications of the other. No jargon is used and terminology is carefully explained.

The book has a very consistent framework and a nice flow from one chapter to the next. As mentioned above, relationships between the two subjects of the title are emphasized.

The book is nicely broken up into manageable sections that would fit well into a lecture course. Interdependences among chapters are clearly indicated.

The topics are presented clearly and logically with relationships among them clearly pointed out and discussed in detail.

All pages display very well on my screen, with no legibility or distortion issues that I could see.

The grammar seems fine.

This is not relevant for a mathematics text, but I saw nothing that would be offensive to a reader of any ethnic background.

I would be happy to teach a course out of this book.

The text is so comprehensive that it feels overwhelming. The author wanted to include all of the mathematics required beyond a standard calculus sequence. However, the mathematical maturity required to read and learn from this text is quite... read more

The text is so comprehensive that it feels overwhelming. The author wanted to include all of the mathematics required beyond a standard calculus sequence. However, the mathematical maturity required to read and learn from this text is quite high. The first two chapters cover much of a standard undergraduate course in number theory, built up from scratch. However, it almost completely lacks numerical examples and computational practice for the students, which would give those new to the material time and experience in which to digest, assimilate, and understand the material. I would think that a book targeted at this level of mathematical sophistication would assume students are comfortable with (for example) the most basic notions of group theory or the idea of equivalence classes. I can't imagine an appropriate audience for this text: one with the ability to read and work entirely at this abstract level but without any (or most) of the mathematical preparation provided in at least half the chapters.

I found no mathematical errors. The mathematical presentation is rigorous, clear, and well-explained. It can be terse at times, skipping steps and making conceptual leaps that will be challenging for all but the very best students.

The book covers both standard background that will always be relevant for these topics: the number theory and algebra background, the probability theory. The computational chapters use pseudocode, so they will not be quickly outdated when new languages become fashionable. Most of the algorithms studied are quite "classical" (as much as that makes sense for computer science), with modern ideas and developments usually relegated to "Notes" at the end of the computational chapters. This will, of course, become outdated with new research in computer science. But any faculty member who keeps up with the relevant research will be able to mention new developments to students, and it will not interrupt the flow of the ideas at all.

The book is exceedingly well written, though it is at a very high level. It is not "friendly" or "chatty" as you will find with many number theory books targeted to undergraduates. For many students this will detract from clarity because they do not yet have the mathematical sophistication to work at this level.

The book does an excellent job of consistency of notation. For example, it starts with a development of number theory concepts, and develops notation for residue classes in the integers modulo n. Later in the chapters on groups and rings, this same notation is used in more general situations. Whenever there is the potential for confusion (for example, in using "a mod b" as a binary operation as is common in computer science versus using "a is congruent to x mod b" as is more standard in mathematics) the author is careful to point out the dual meanings and to warn the reader that there is some overloading of terminology. It is unavoidable that this will happen in any book that treats both subjects seriously, and the author is careful with notation and keeps potential confusion to a minimum.

The book has 21 chapters, each with several sections. Most, but not all, sections end with a set of exercises. Essential exercises are underlined (a very nice feature!) and optional sections are indicated with an asterisk. What would be helpful would be some suggested paths through the text for various purposes. I don't think it would be appropriate in any class to start at Chapter 1 and and work through all (or even most) of the content. I imagine that most classes would skip the background material and head straight for the computational chapters, with the background there "as needed" for the students.

My main comment about the structure is that the mathematics chapters and the computational chapters seem to be separated. For example, the chapter on "Congruences" covers a tremendous amount of number theory, not all of which falls naturally (in my mind) under that heading. Chapter 1 has a section on "Ideals and greatest common divisors," but Euclid's Algorithm is not tackled until Chapter 4 (a more computational chapter). As I read, I often felt "now we are doing mathematics... now we are concerned with computational questions." There are natural places of overlap (like Euclid's algorithm), and they are separated rather than treated more holistically.

I read a standard PDF file. There were a few hyperlinks (from the table of contents to section headings, for example), but not much else in the way of interface. Everything was rendered clearly.

I found no errors.

There is a lot of interesting history and "cultural" notes in the computing chapters, and almost none in the more mathematical chapters. A student who studied from this text would miss a lot of the standard "mathematics culture" communicated in a more traditional number theory course.

My primary comment is that I cannot pin down the audience for this book. I could not use this in an undergraduate number theory class; it is at far too high a level and moves far too quickly. I could not use it in a graduate number theory class; it assumes no background at all and does not do some standard topics. I suppose it would be useful for self-study by a very advanced student who already knew a good deal of mathematics and wanted to explore the computational side. I do think that the title "A Computational Introduction to Number Theory and Algebra" is misleading at best. Lacking numerical examples (for examples, students never actually do any "clock arithmetic" type calculations when introduced to the integers mod n) and with a focus only on abelian groups and commutative rings with unity, the book is simultaneously too sophisticated and not sophisticated enough for my use. It also has a bit of a "joyless" feel in the mathematics, with a development of ideas and a writing style that never brings students into any part of the discovery of the mathematics.

## Table of Contents

- 1 Basic properties of the integers
- 2 Congruences
- 3 Computing with large integers
- 4 Euclid's algorithm
- 5 The distribution of primes
- 6 Abelian groups
- 7 Rings
- 8 Finite and discrete probability distributions
- 9 Probabilistic algorithms
- 10 Probabilistic primality testing
- 11 Finding generators and discrete logarithms in Z∗p
- 12 Quadratic reciprocity and computing modular square roots
- 13 Modules and vector spaces
- 14 Matrices
- 15 Subexponential-time discrete logarithms and factoring
- 16 More rings
- 17 Polynomial arithmetic and applications
- 18 Finite Fields
- 19 Linearly generated sequences and applications
- 20 Algorithms for finite fields
- 21 Deterministic primality testing

## About the Book

All of the mathematics required beyond basic calculus is developed “from scratch.” Moreover, the book generally alternates between “theory” and “applications”: one or two chapters on a particular set of purely mathematical concepts are followed by one or two chapters on algorithms and applications; the mathematics provides the theoretical underpinnings for the applications, while the applications both motivate and illustrate the mathematics. Of course, this dichotomy between theory and applications is not perfectly maintained: the chapters that focus mainly on applications include the development of some of the mathematics that is specific to a particular application, and very occasionally, some of the chapters that focus mainly on mathematics include a discussion of related algorithmic ideas as well.

The mathematical material covered includes the basics of number theory (including unique factorization, congruences, the distribution of primes, and quadratic reciprocity) and of abstract algebra (including groups, rings, fields, and vector spaces). It also includes an introduction to discrete probability theory—this material is needed to properly treat the topics of probabilistic algorithms and cryptographic applications. The treatment of all these topics is more or less standard, except that the text only deals with commutative structures (i.e., abelian groups and commutative rings with unity) — this is all that is really needed for the purposes of this text, and the theory of these structures is much simpler and more transparent than that of more general, non-commutative structures.

- There are a few sections that are marked with a “(∗),” indicating that the material covered in that section is a bit technical, and is not needed else- where.
- There are many examples in the text, which form an integral part of the book, and should not be skipped.
- There are a number of exercises in the text that serve to reinforce, as well as to develop important applications and generalizations of, the material presented in the text.
- Some exercises are underlined. These develop important (but usually simple) facts, and should be viewed as an integral part of the book. It is highly recommended that the reader work these exercises, or at the very least, read and understand their statements.
- In solving exercises, the reader is free to use any previously stated results in the text, including those in previous exercises. However, except where otherwise noted, any result in a section marked with a “(∗),” or in §5.5, need not and should not be used outside the section in which it appears.
- There is a very brief “Preliminaries” chapter, which fixes a bit of notation and recalls a few standard facts. This should be skimmed over by the reader.
- There is an appendix that contains a few useful facts; where such a fact is used in the text, there is a reference such as “see §An,” which refers to the item labeled “An” in the appendix.

## About the Contributors

### Author

**Victor Shoup** is a Professor in the Department of Computer Science at the Courant Institute of Mathematical Sciences, New York University.