The joy of factoring (Q2863722)

The present book is a summary of the state of the knowledge in integer factorization. With the emphasis in motivating the problem and placing it in a historical perspective, the book gives a survey of the main factoring algorithms, from trial division to the current methods like those based on elliptic curves or the Number Field Sieve algorithm. It also includes the mathematical foundations and tools supporting those algorithms.NEWLINENEWLINEChapters 1 and 4 are devoted to motivate the interest and applications of the factorization of integers, while Chapters 2 and 3 gather the necessary results from number theory. The following four chapters discuss different methods of factoring: Chapter 5 provides some \textit{elementary} methods (from trial division to Pollard's \(p-1\)), Chapter 6 studies factoring methods based on continued fractions, Chapter 7 discusses Lenstra's factoring algorithm (and also the elliptic primality tests of Goldwasser-Kilian and Atkin-Morain) and Chapter 8 deals with sieve algorithms in particular the quadratic and Number Field Sieves, the today fastest factoring algorithms.NEWLINENEWLINEChapter 9 describes (and illustrates with pictures) some historical devices and modern computers to perform factoring algorithms as well as two possible methods for the future: quantum and DNA factoring. The last Chapter 10 discusses some related topics as the computational complexity of factoring or how to factor a RSA public key.NEWLINENEWLINEThe book, ``intended for readers who have taken an introductory number theory course'', is as self-contained as possible, with references to the wide bibliography when necessary. Algorithms are usually given in pseudocode and also described in words.NEWLINENEWLINEThe book is well written and easy to read, many examples are provided through the text and, at the end of each chapter, exercises are included, with solutions or hints for some of them at the end of the book.