mersenneforum.org The Joy of Factoring - book review
 Register FAQ Search Today's Posts Mark Forums Read

 2014-07-05, 01:05 #1 philmoore     "Phil" Sep 2002 Tracktown, U.S.A. 45F16 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 257885161-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     Jun 2011 Thailand 25·5·59 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
 2014-12-13, 09:52 #3 Xyzzy     "Mike" Aug 2002 11111110110102 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? 2014-12-13, 10:59 #4 davar55 May 2004 New York City 3·17·83 Posts 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?

 2015-01-01, 16:50 #5 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT/BST) 133558 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.
2015-01-22, 15:17   #6
bdodson

Jun 2005
lehigh.edu

210 Posts

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

2016-10-13, 05:34   #7
CRGreathouse

Aug 2006

135418 Posts

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. 2016-10-13, 05:39 #8 CRGreathouse Aug 2006 32×5×7×19 Posts 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) 2016-10-21, 01:10 #9 Jeff Gilchrist Jun 2003 Ottawa, Canada 3×17×23 Posts 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post firejuggler GPU Computing 29 2016-11-15 19:16 Fred Hardware 7 2016-02-12 16:19 wblipp Math 49 2012-02-12 11:43 Primeinator Analysis & Analytic Number Theory 15 2011-01-12 23:05 Numbers Lounge 5 2005-09-30 17:53

All times are UTC. The time now is 02:32.

Sun May 9 02:32:49 UTC 2021 up 30 days, 21:13, 0 users, load averages: 2.00, 1.69, 1.57