The Joy of Factoring - book review

philmoore · 2014-07-05, 01:05

I just finished reading The Joy of Factoring by Samuel Wagstaff, Jr., published 2013 by the American Mathematical Society (AMS), and wanted to pass on a recommendation of this book to Forum members. For readers who have studied Prime Numbers, a Computational Perspective by Crandall and Pomerance, the level of Wagstaff's book is much more at the introductory level. Descriptions of various algorithms are presented in pseudo-code along with numerical examples so that a beginner will get a good idea of the principles on which each factoring method is based, and should be able to write at least a program implementing the basic algorithms. However, the more advanced topics of optimizing the algorithms are in general only pointed at through references, and a serious attempt at writing a polished piece of code may need to go beyond the material presented in this book. However, Wagstaff does an admirable job of describing the why of factoring as well as the how, and for that reason alone, I think many readers of this Forum will enjoy it.

Chapter 1, entitled Why Factor Integers? contains brief discussions of Public Key Cryptography, repunits, the Cunningham Project, repeating decimal fractions, and perfect numbers as motivations for why one might want to factor numbers. Chapters 2 and 3 present a review of basic number theory and number theory topics relevant to factoring that are useful in understanding the rest of the book. Theorems are carefully stated, some of these theorems are proved, and others are not proved but the reader is given references to other works in which complete proofs are given. Chapter 4, entitled How Are Factors Used? goes in to more detail in diverse topics, including applications to cryptography, pseudo-random bit stream generation, Aurifeuillian factors, perfect numbers and aliquot sequences, Bell and Bernoulli numbers, primality proving, and testing of conjectures. Factoring methods are discussed in chapters 5 through 8 with "simple" algorithms in chapter 5, methods based on continued fractions in chapter 6, factoring and primality proving based on elliptic curves in chapter 7, and sieve algorithms in chapter 8. The treatment of the Number Field Sieve is sketchy at best, and is apparently not intended to give a beginner enough information to attempt to program it, but the numerical examples and discussion of choosing suitable polynomials should at least give the interested neophyte a feel for what all is involved. Chapter 9 discusses special-purpose factoring devices, both historical devices that have actually been built as well as proposed devices that currently exist only as concepts. The final chapter 10, entitled Theoretical and Practical Factoring, contains a diverse collection of sections covering complexity theory, multi-precision arithmetic, dirty tricks that may succeed in breaking RSA public key cryptography when the keys are not carefully chosen, and the future of factoring. An excellent and extensive bibliography follows. There is probably something in here for anyone who frequents this forum, and a number of Forum participants are even cited for factoring work they have done. My only beef with Sam Wagstaff is that he did not mention GIMPS, although he does discuss perfect numbers and Mersenne primes, including 2^57885161-1. Even though GIMPS is primarily a prime hunting project, as opposed to a factoring project, the fact that factoring is an important part of GIMPS, eliminating five-eighths of potential candidates, would have made it a good tie-in to the theme of this book.

Although the book is available from mega-online-booksellers, I have found the price is nearly the same if you order from the AMS, a non-profit organization devoted to mathematics research and education, and would recommend that you order it directly from them:
http://www.ams.org/bookstore-getitem?item=STML-68

LaurV · 2014-07-05, 06:20

Thank you for recommendation. Good posting too. I added it to the list.

Xyzzy · 2014-12-13, 09:52

We noticed that it is available here: https://books.google.com/books?id=rowCAQAAQBAJ

Unfortunately, it is still not available for the Kindle.

Do authors receive the same amount of $ for digital sales as they do for dead-tree sales?

davar55 · 2014-12-13, 10:59

Quote:

Originally Posted by Xyzzy

We noticed that it is available here: https://books.google.com/books?id=rowCAQAAQBAJ

Unfortunately, it is still not available for the Kindle.

Do authors receive the same amount of $ for digital sales as they do for dead-tree sales?

Some of us don't use Kindle yet. Do you mean per sale item or total?

henryzz · 2015-01-01, 16:50

Received this book yesterday. It seems to be very good at explaining each of the various factoring methods available in a way that is understandable to a wide range of people. Prior to reading this book I have been unable to understand how ECM works. This book explains how it is similar to P-1, how it works and gives examples.
While this book might not go into enough detail to fully understand NFS it does provide a lot of the maths behind it and gives a general picture.

In general this book is a good stepping stone to understanding the algorithms it describes. To implement many of them efficiently it would require reading a more advanced book such as Prime Numbers, a Computational Perspective by Crandall and Pomerance.

bdodson · 2015-01-22, 15:17

Quote:

Originally Posted by henryzz

Received this book yesterday. It seems to be very good at explaining each of the various factoring methods available in a way that is understandable to a wide range of people.
...
To implement many of them efficiently it would require reading a more advanced book such as Prime Numbers, a Computational Perspective by Crandall and Pomerance.

The review on Math Reviews (with mathscinet license) is written by Carl. The relation
between p-1 and ECM is explained clearly in Koblitz's Course in Number Theory and
Crypto 1994. Hendrik's original observation follows Pollard (cf. the review of Hendrik's
Annals paper 1987), which is somewhat more complicated. -Bruce Dodson

from Math Reviews:

Quote:

.. this book is more at home in describing factorization algorithms from the perspective of
actually implementing them. In particular, heuristic analyses of the principal factoring
algorithms are not fully developed. The book's strengths lie in clear descriptions of
the algorithms (most of which are given in easily readable pseudocode), the historical
details, and the obvious enthusiasm of the author. Where else would you find an exercise
such as this: "Multiply 2071723 x 5363222357 by hand. Feel the joy."
-Carl Pomerance

CRGreathouse · 2016-10-13, 05:34

Quote:

Originally Posted by Xyzzy

Do authors receive the same amount of $ for digital sales as they do for dead-tree sales?

Generally I think the answer is "yes". The main reason books aren't available on Kindle, AFAIK, is the conversion cost. I don't know how this is handled.

CRGreathouse · 2016-10-13, 05:39

Quote:

Originally Posted by bdodson

The review on Math Reviews (with mathscinet license) is written by Carl. The relation
between p-1 and ECM is explained clearly in Koblitz's Course in Number Theory and
Crypto 1994. Hendrik's original observation follows Pollard (cf. the review of Hendrik's
Annals paper 1987), which is somewhat more complicated. -Bruce Dodson

There's also a review by William Gasarch in June's ACM SIGACT News:
http://mathcs.clarku.edu/~fgreen/SIG...okrev/47-2.pdf (pages 7-8 in the pdf)

Jeff Gilchrist · 2016-10-21, 01:10

Quote:

Originally Posted by Xyzzy

Do authors receive the same amount of $ for digital sales as they do for dead-tree sales?

I was just talking to an author about that. In his case he gets almost double for e-book sales because the publisher has no re-curring printing costs. That is double of an already very small number for each book.

2014-07-05, 01:05	#1
philmoore "Phil" Sep 2002 Tracktown, U.S.A. 19·59 Posts	The Joy of Factoring - book review I just finished reading The Joy of Factoring by Samuel Wagstaff, Jr., published 2013 by the American Mathematical Society (AMS), and wanted to pass on a recommendation of this book to Forum members. For readers who have studied Prime Numbers, a Computational Perspective by Crandall and Pomerance, the level of Wagstaff's book is much more at the introductory level. Descriptions of various algorithms are presented in pseudo-code along with numerical examples so that a beginner will get a good idea of the principles on which each factoring method is based, and should be able to write at least a program implementing the basic algorithms. However, the more advanced topics of optimizing the algorithms are in general only pointed at through references, and a serious attempt at writing a polished piece of code may need to go beyond the material presented in this book. However, Wagstaff does an admirable job of describing the why of factoring as well as the how, and for that reason alone, I think many readers of this Forum will enjoy it. Chapter 1, entitled Why Factor Integers? contains brief discussions of Public Key Cryptography, repunits, the Cunningham Project, repeating decimal fractions, and perfect numbers as motivations for why one might want to factor numbers. Chapters 2 and 3 present a review of basic number theory and number theory topics relevant to factoring that are useful in understanding the rest of the book. Theorems are carefully stated, some of these theorems are proved, and others are not proved but the reader is given references to other works in which complete proofs are given. Chapter 4, entitled How Are Factors Used? goes in to more detail in diverse topics, including applications to cryptography, pseudo-random bit stream generation, Aurifeuillian factors, perfect numbers and aliquot sequences, Bell and Bernoulli numbers, primality proving, and testing of conjectures. Factoring methods are discussed in chapters 5 through 8 with "simple" algorithms in chapter 5, methods based on continued fractions in chapter 6, factoring and primality proving based on elliptic curves in chapter 7, and sieve algorithms in chapter 8. The treatment of the Number Field Sieve is sketchy at best, and is apparently not intended to give a beginner enough information to attempt to program it, but the numerical examples and discussion of choosing suitable polynomials should at least give the interested neophyte a feel for what all is involved. Chapter 9 discusses special-purpose factoring devices, both historical devices that have actually been built as well as proposed devices that currently exist only as concepts. The final chapter 10, entitled Theoretical and Practical Factoring, contains a diverse collection of sections covering complexity theory, multi-precision arithmetic, dirty tricks that may succeed in breaking RSA public key cryptography when the keys are not carefully chosen, and the future of factoring. An excellent and extensive bibliography follows. There is probably something in here for anyone who frequents this forum, and a number of Forum participants are even cited for factoring work they have done. My only beef with Sam Wagstaff is that he did not mention GIMPS, although he does discuss perfect numbers and Mersenne primes, including 2^57885161-1. Even though GIMPS is primarily a prime hunting project, as opposed to a factoring project, the fact that factoring is an important part of GIMPS, eliminating five-eighths of potential candidates, would have made it a good tie-in to the theme of this book. Although the book is available from mega-online-booksellers, I have found the price is nearly the same if you order from the AMS, a non-profit organization devoted to mathematics research and education, and would recommend that you order it directly from them: http://www.ams.org/bookstore-getitem?item=STML-68

2014-07-05, 06:20	#2
LaurV Romulan Interpreter "name field" Jun 2011 Thailand 24060₈ Posts	Thank you for recommendation. Good posting too. I added it to the list. Last fiddled with by LaurV on 2014-07-05 at 06:22

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
GTX 1070 8gb review	firejuggler	GPU Computing	29	2016-11-15 19:16
PicoPSU Review	Fred	Hardware	7	2016-02-12 16:19
Review of Odd Perfect Paper	wblipp	Math	49	2012-02-12 11:43
Review of calculus/ODE	Primeinator	Analysis & Analytic Number Theory	15	2011-01-12 23:05
Book Review	Numbers	Lounge	5	2005-09-30 17:53

2014-12-13, 09:52	#3
Xyzzy Aug 2002 5·11·157 Posts	We noticed that it is available here: https://books.google.com/books?id=rowCAQAAQBAJ Unfortunately, it is still not available for the Kindle. Do authors receive the same amount of $ for digital sales as they do for dead-tree sales?

2015-01-01, 16:50	#5
henryzz Just call me Henry "David" Sep 2007 Liverpool (GMT/BST) 6125₁₀ Posts	Received this book yesterday. It seems to be very good at explaining each of the various factoring methods available in a way that is understandable to a wide range of people. Prior to reading this book I have been unable to understand how ECM works. This book explains how it is similar to P-1, how it works and gives examples. While this book might not go into enough detail to fully understand NFS it does provide a lot of the maths behind it and gives a general picture. In general this book is a good stepping stone to understanding the algorithms it describes. To implement many of them efficiently it would require reading a more advanced book such as Prime Numbers, a Computational Perspective by Crandall and Pomerance.