Author	Riesel, Hans. author
Title	Prime Numbers and Computer Methods for Factorization [electronic resource] / by Hans Riesel
Imprint	Boston, MA : Birkhรคuser Boston : Imprint: Birkhรคuser, 1985
Connect to	http://dx.doi.org/10.1007/978-1-4757-1089-2
Descript	XVI, 464 p. online resource

In this book the author treats four fundamental and apparently simple problems. They are: the number of primes below a given limit, the apยญ proximate number of primes, the recognition of prime numbers and the factorization of large numbers. A chapter on the details of the distribution of the primes is included as well as a short description of a recent applicaยญ tion of prime numbers, the so-called RSA public-key cryptosystem. The author is also giving explicit algorithms and computer programs. Whilst not claiming completeness, the author has tried to give all important results known, including the latest discoveries. The use of computers has in this area promoted a development which has enormously enlarged the wealth of results known and that has made many older works and tables obsolete. As is often the case in number theory, the problems posed are easy to understand but the solutions are theoretically advanced. Since this text is aimed at the mathematically inclined layman, as well as at the more advanced student, not all of the proofs of the results given in this book are shown. Bibliographical references in these cases serve those readers who wish to probe deeper. References to recent original works are also given for those who wish to pursue some topic further. Since number theory is seldom taught in basic mathematics courses, the author has appended six sections containing all the algebra and number theory required for the main body of the book

1. The Number of Primes Below a Given Limit -- 2. The Primes Viewed at Large -- 3. Subtleties in the Distribution of Primes -- 4. The Recognition of Primes -- 5. Factorization -- 6. Prime Numbers and Cryptography -- Appendix 1. Basic Concepts in Higher Algebra -- Modules -- Euclidโ{128}{153}s Algorithm -- The Labour Involved in Euclidโ{128}{153}s Algorithm -- A Definition Taken from the Theory of Algorithms -- A Computer Program for Euclidโ{128}{153}s Algorithm -- Reducing the Labour -- Binary Form of Euclidโ{128}{153}s Algorithm -- Groups -- Lagrangeโ{128}{153}s Theorem. Cosets -- Abstract Groups. Isomorphic Groups -- The Direct Product of Two Given Groups -- Cyclic Groups -- Rings -- Zero Divisors -- Fields -- Mappings. Isomorphisms and Homomorphisms -- Group Characters -- The Conjugate or Inverse Character -- Homomorphisms and Group Characters -- Appendix 2. Basic Concepts in Higher Arithmetic -- Divisors. Common Divisors -- The Fundamental Theorem of Arithmetic -- Congruences -- Linear Congruences -- Linear Congruences and Euclidโ{128}{153}s Algorithm -- Systems of Linear Congruences -- Carmichaelโ{128}{153}s Function -- Carmichaelโ{128}{153}s Theorem -- Appendix 3. Quadratic Residues -- Legendreโ{128}{153}s Symbol. -- Arithmetic Rules for Residues and Non-Residues -- The Law of Quadratic Reciprocity -- Jacobiโ{128}{153}s Symbol -- Appendix 4. The Arithmetic of Quadratic Fields -- Appendix 5. Continued Fractions -- What Is a Continued Fraction? -- Regular Continued Fractions. Expansions -- Evaluating a Continued Fraction -- Continued Fractions as Approximations -- Euclidโ{128}{153}s Algorithm and Continued Fractions -- Linear Diophantine Equations and Continued Fractions -- A Computer Program -- Continued Fraction Expansions of Square Roots -- Proof of Periodicity -- The Maximal Period-Lenath -- Short Periods -- Continued Fractions and Quadratic Residues -- Appendix 6. Algebraic Factors -- Factorization of Polynomials -- The Cyclotomic Polynomials -- Aurifeuillian Factorizations -- Factorization Formulas -- The Algebraic Structure of Aurifeuillian Numbers -- Appendix 7. Multiple-Precision Arithmetic -- Various Objectives for a Multiple-Precision Package -- How to Store Multi-Precise Integers -- Addition and Subtraction of Multi-Precise Integers -- Reduction in Length of Multi-Precise Integers -- Multiplication of Multi-Precise Integers -- Division of Multi-Precise Integers -- Input and Output of Multi-Precise Integers -- A Complete Package for Multiple-Precision Arithmetic -- Appendix 8. Fast Multiplication of Large Integers -- The Ordinary Multiplication Algorithm. -- Double Length Multiplication. -- Recursive Use of Double Length Multiplication Formula -- A Recursive Procedure for Squaring Large Integers -- Fractal Structure of Recursive Squaring -- Large Mersenne Primes -- Appendix 9. The Stieltjes Integral -- Functions With Jump Discontinuities -- The Riemann Integral -- Definition of the Stieltjes Integral -- Rules of Integration for Stieltjes Integrals -- Integration by Parts of Stieltjes Integrals -- The Mean Value Theorem -- Applications -- Tables -- Tatle 1. The Primes Belnw 12553 -- Table 4. Factors of Fermat Numbers -- Table 7. Factors of Mersenne Numbers -- Table 32. Quadratic Residues -- Table 33. Gaussโ{128}{153} formulas for Cyclotomic Polynomials -- Table 34. Lucasโ{128}{153} formulas for Cyclotomic Polynomials