20140705, 01:05  #1 
"Phil"
Sep 2002
Tracktown, U.S.A.
1119_{10} 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 pseudocode 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, pseudorandom 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 specialpurpose 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, multiprecision 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 fiveeighths of potential candidates, would have made it a good tiein to the theme of this book. Although the book is available from megaonlinebooksellers, I have found the price is nearly the same if you order from the AMS, a nonprofit organization devoted to mathematics research and education, and would recommend that you order it directly from them: http://www.ams.org/bookstoregetitem?item=STML68 
20140705, 06:20  #2 
Romulan Interpreter
Jun 2011
Thailand
2×3×7×233 Posts 
Thank you for recommendation. Good posting too. I added it to the list.
Last fiddled with by LaurV on 20140705 at 06:22 
20141213, 09:52  #3 
Aug 2002
10000001110110_{2} 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 deadtree sales? 
20141213, 10:59  #4  
May 2004
New York City
1000010001011_{2} Posts 
Quote:


20150101, 16:50  #5 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
1011100100000_{2} 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 P1, 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. 
20150122, 15:17  #6  
Jun 2005
lehigh.edu
2^{10} Posts 
Quote:
between p1 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:


20161013, 05:34  #7 
Aug 2006
13533_{8} Posts 

20161013, 05:39  #8  
Aug 2006
3·1,993 Posts 
Quote:
http://mathcs.clarku.edu/~fgreen/SIG...okrev/472.pdf (pages 78 in the pdf) 

20161021, 01:10  #9 
Jun 2003
Ottawa, Canada
3·17·23 Posts 
I was just talking to an author about that. In his case he gets almost double for ebook sales because the publisher has no recurring printing costs. That is double of an already very small number for each book.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
GTX 1070 8gb review  firejuggler  GPU Computing  29  20161115 19:16 
PicoPSU Review  Fred  Hardware  7  20160212 16:19 
Review of Odd Perfect Paper  wblipp  Math  49  20120212 11:43 
Review of calculus/ODE  Primeinator  Analysis & Analytic Number Theory  15  20110112 23:05 
Book Review  Numbers  Lounge  5  20050930 17:53 