## The Joy of FactoringThis book is about the theory and practice of integer factorisation presented in a historic perspective. It describes about twenty algorithms for factoring and a dozen other number theory algorithms that support the factoring algorithms. Most algorithms are described both in words and in pseudocode to satisfy both number theorists and computer scientists. Each of the ten chapters begins with a concise summary of its contents. The book starts with a general explanation of why factoring integers is important. The next two chapters present number theory results that are relevant to factoring. Further on there is a chapter discussing, in particular, mechanical and electronic devices for factoring, as well as factoring using quantum physics and DNA molecules. Another chapter applies factoring to breaking certain cryptographic algorithms. Yet another chapter is devoted to practical vs. theoretical aspects of factoring. The book contains more than 100 examples illustrating various algorithms and theorems. It also contains more than 100 interesting exercises to test the reader's understanding. Hints or answers are given for about a third of the exercises.The book concludes with a dozen suggestions of possible new methods for factoring integers. This book is written for readers who want to learn more about the best methods of factoring integers, many reasons for factoring, and some history of this fascinating subject. It can be read by anyone who has taken a first course in number theory. |

### Contents

1 | |

Number Theory Review | 13 |

Number Theory Relevant to Factoring | 41 |

How Are Factors Used? | 75 |

Simple Factoring Algorithms | 119 |

Continued Fractions | 143 |

Elliptic Curves | 173 |

### Common terms and phrases

Alice arithmetic Aurifeuillian factorization B-smooth Carmichael number CFRAC Chapter Chinese Remainder Theorem choose cipher composite number compute continued fraction cryptography Cunningham Project Cunningham table decimal digits Elliptic Curve Method enciphering equation Euler’s Example Extended Euclidean Algorithm factor base factoring integers Factoring Method faster ﬁrst formula function gcd(m greatest common divisor harmonic numbers input integer factoring irreducible large integers large numbers large primes least Legendre symbol Lehmer Lemma Lenstra linear algebra loop multiple Number Field Sieve number theory odd perfect number odd prime Output Pollard Pomerance primality test prime factors prime number primitive root probabilistic probable prime problem proof proper factor proved pseudoprime to base public key quadratic nonresidue quadratic residue modulo Quadratic Sieve random numbers rational number real number relations relatively prime Section shows solution solve square free square roots SQUFOF strong pseudoprime Suppose Trial Division vector y2 mod