You are here

The Joy of Factoring

Samuel S. Wagstaff, Jr.
American Mathematical Society
Publication Date: 
Number of Pages: 
Student Mathematical Library 68
[Reviewed by
Mark Hunacek
, on

It is, I think, a fairly safe bet that most students learning about factoring do not instinctively view the subject as having anything whatsoever to do with “joy”. Other well-known books with titles beginning “The joy of…”, like The Joy of Sex and The Joy of Cooking, come equipped with a ready-made constituency that is predisposed to think of the activities described in the title as interesting and pleasant, but, by contrast, most people (even many math students) equate factoring with tedium. Consequently, anybody setting out to write a book entitled The Joy of Factoring is automatically faced with a double objective. The author must not only teach the reader something about factoring, but must also explain why anybody should care. The book under review succeeds on both counts.

An advertising blurb on the back cover of the book says that it “can be read by anyone who has taken a first course in number theory”. This seems overly optimistic: in addition to number theory, some prior background in calculus, linear algebra and abstract algebra would be useful. In addition, while no particular programming knowledge is required because the author presents algorithms in pseudocode, some ability to read and understand these is also necessary. Nevertheless, while I think the quoted statement is stretching things a bit, I do believe a good undergraduate junior or senior mathematics or computer science major should find this text accessible.

The book begins with a chapter entitled “Why Factor Integers?” which directly addresses the second of the two objectives I referred to in the first paragraph above. In this chapter the author gives an expository overview of areas in which factoring is used, starting, not surprisingly, with the most obvious one: public-key cryptography. The section on cryptography surveys the Data Encryption Standard, the important 1976 paper of Diffie and Hellman, and the development of the RSA system, which depends on the fact that factoring large numbers is difficult. Other sections in this first chapter discuss applications of factoring to repunits (numbers consisting entirely of 1s), the study of perfect numbers and the period of decimal expansions of fractions. The chapter concludes with a section on the Cunningham Project, a collection of tables showing the factorizations of numbers of the form bn + 1 and bn -1 for various values of b and n. (The author maintains the latest versions of the tables on a webpage that is cited in the book; he describes the project as the “largest factoring enterprise in the world today”.)

The second and third chapters address necessary background in number theory — first, in chapter 2, the basics of the subject (divisibility, primes, congruences, etc.), reviewed quickly and mostly without proof; and then, in chapter 3, some topics that are more advanced and less likely to have been seen before by the student in an introductory number theory course (including divisibility sequences, Carmichael numbers, primality testing, cyclotomic polynomials, factors of Fibionacci and Lucas numbers).

Chapter 4 returns to the theme of chapter 1 and gives more information as to the uses of factorization. Cryptography and perfect numbers are looked at in more detail than they were in the first chapter, and other uses of factorization are given as well.

The rest of the book, chapters five through ten, give lots of methods of factoring, proceeding in roughly chronological order from the early slow methods to methods that are more efficient and use more sophisticated mathematics. Elliptic curves, for example, are discussed in chapter 7; this chapter presupposes some background in abstract algebra, but does not assume any prior acquaintance with elliptic curves themselves, which are defined from scratch and then used to give factoring and primality testing algorithms. Likewise, continued fractions and their applications to factoring algorithms are the subject of chapter 6; the author does not assume prior knowledge of continued fractions either, and also defines them from scratch, but the exposition is fairly rapid. In both chapters 6 and 7, some but by no means all theorems are proved, but references are provided when a proof is not. The basic approach in this part of the part of the book is to give the algorithms, discuss them, and provide examples.

Chapters 9 and 10, the last two chapters of the text, struck me as particularly interesting. The first of these discusses devices — hardware, not software — for factoring numbers, some of them actually constructed and others merely proposed. (Photographs of some of these devices, from the 1920s and 1930s, are included.) The chapter ends with a brief discussion of quantum computing.

The final chapter of the book is entitled “Theoretical and Practical Factoring”; some of the algorithms discussed in the book, for example, have worked in practice but have not yet been shown to be valid in general. This chapter addresses both issues by giving some theoretical results about the complexity of factoring algorithms, and also some practical results. The chapter ends with a very interesting section on the author’s views of the future of factoring, in which he attempts to “predict the future by looking at the past”. It turns out that from 1970 to 1995, every five years or so have brought with it a genuine advance in factoring algorithms, but since then there have been no faster algorithms (although people have invented ways of creating faster programs for existing algorithms, no algorithms with faster asymptotic complexity have been discovered). The author ends the book with a list of suggestions as to how one might go about discovering one.

To facilitate the use of this book as a text, the author has provided exercises at the end of each chapter, solutions or hints to some of them appearing in a short (four-page) Appendix. Another valuable feature of the book is a very extensive bibliography.

I think a second course in number theory, or senior seminar, based on this book would be quite interesting. A professor of an introductory course in number theory might also want to have this book close at hand for occasional classroom comments or tidbits of information. (Want to know, for example, what the largest Fermat number to be completely factored is? This book tells you: F11.) The book could also be used as a text for an upper-level course in computer science for students with some background in number theory. It also certainly belongs in any good university library, if only because the material collected in it is not (to my knowledge at any rate) readily available in the textbook literature.

Mark Hunacek ( teaches mathematics at Iowa State University.