Riesel H. Prime Numbers and Computer Methods for Factorization

2nd ed. — N.Y.: Springer, 2012. — XVIII, 464 p. 20 ill. — (Modern Birkhäuser Classics) — ISBN: 978-08176-8297-2, e-ISBN: 978-0-8176-8298-9.Affordable reprint of the successful, expanded second edition of a unique monograph
Provides a unique perspective on the study of prime numbers and their importance in modern technology
Applications remain relevant across the fields of modern computer science and information transmissionAbout this book:
In the modern age of almost universal computer usage, practically every individual in a technologically developed society has routine access to the most up-to-date cryptographic technology that exists, the so-called RSA public-key cryptosystem. A major component of this system is the factorization of large numbers into their primes. Thus an ancient number-theory concept now plays a crucial role in communication among millions of people who may have little or no knowledge of even elementary mathematics.Hans Riesel’s highly successful first edition of this book has now been enlarged and updated with the goal of satisfying the needs of researchers, students, practitioners of cryptography, and non-scientific readers with a mathematical inclination. It includes important advances in computational prime number theory and in factorization as well as re-computed and enlarged tables, accompanied by new tables reflecting current research by both the author and his coworkers and by independent researchers.The book treats four fundamental problems: the number of primes below a given limit, the approximate number of primes, the recognition of primes and the factorization of large numbers. The author provides explicit algorithms and computer programs, and has attempted to discuss as many of the classically important results as possible, as well as the most recent discoveries. The programs include are written in PASCAL to allow readers to translate the programs into the language of their own computers.The independent structure of each chapter of the book makes it highly readable for a wide variety of mathematicians, students of applied number theory, and others interested in both study and research in number theory and cryptography.Preface

NotationThe Number of Primes Below a Given Limit
What Is a Prime Number?
The Fundamental Theorem of Arithmetic
Which Numbers Are Primes? The Sieve of Eratosthenes
General Remarks Concerning Computer Programs
A Sieve Program
Compact Prime Tables
Hexadecimal Compact Prime Tables
Difference Between Consecutive Primes
The Number of Primes Below x
Meissel’s Formula
Evaluation of Pk(x, a)
Lehmer’s Formula
Computations
A Computation Using Meissel’s Formula
A Computation Using Lehmer’s Formula
A Computer Program Using Lehmer’s Formula
Mapes’ Method
Deduction of Formulas
A Worked Example
Mapes’ Algorithm
Programming Mapes’ Algorithm
Recent Developments
Results
Computational Complexity
Comparison Between the Methods DiscussedThe Primes Viewed at LargeNo Polynomial Can Produce Only Primes
Formulas Yielding All Primes
The Distribution of Primes Viewed at Large. Euclid’s Theorem
The Formulas of Gauss and Legendre for π(x). The Prime Number Theorem
The Chebyshev Function θ(x)
The Riemann Zeta-function
The Zeros of the Zeta-function
Conversion From f(x) Back to π(x)
The Riemann Prime Number Formula
The Sign of li(x) − π(x)
The Influence of the Complex Zeros of ζ(s) on π(x)
The Remainder Term in the Prime Number Theorem
Effective Inequalities for π(x), p_n, and θ(x)
The Number of Primes in Arithmetic ProgressionsSubtleties in the Distribution of Primes
The Distribution of Primes in Short Intervals
Twins and Some Other Constellations of Primes
Admissible Constellations of Primes
The Hardy-Littlewood Constants
The Prime k-Tuples Conjecture
Theoretical Evidence in Favour of the Prime k-Tuples Conjecture
Numerical Evidence in Favour of the Prime k-Tuples Conjecture
The Second Hardy-Littlewood Conjecture
The Midpoint Sieve
Modification of the Midpoint Sieve
Construction of Superdense Admissible Constellations
Some Dense Clusters of Primes
The Distribution of Primes Between the Two Series 4n+1 and 4n+3
Graph of the Function π_4,3(x)−π_4,1(x)
The Negative Regions
The Negative Blocks
Large Gaps Between Consecutive Primes
The Cramér ConjectureThe Recognition of PrimesTests of Primality and of Compositeness
Factorization Methods as Tests of Compositeness
Fermat's Theorem as Compositeness Test
Fermat's Theorem as Primality Test
Pseudoprimes and Probable Primes
A Computer Program for Fermat’s Test
The Labor Involved in a Fermat Test
Carmichael Numbers
Euler Pseudoprimes
Strong Pseudoprimes and a Primality Test
A Computer Program for Strong Pseudoprime Tests
Counts of Pseudoprimes and Carmichael Numbers
Rigorous Primality Proofs
Lehmer’s Converse of Fermat’s Theorem
Formal Proof of Theorem 4.3
Ad Hoc Search for a Primitive Root
The Use of Several Bases
Fermat Numbers and Pepin’s Theorem
Cofactors of Fermat Numbers
Generalized Fermat Numbers
A Relaxed Converse of Fermat’s Theorem
Proth’s Theorem
Tests of Compositeness for Numbers of the form Ν = h·2n±k
An Alternative Approach
Certificates of Primality
Primality Tests of Lucasian Type
Lucas Sequences
The Fibonacci Numbers
Large Subscripts
An Alternative Deduction
Divisibility Properties of the Numbers Un
Primality Proofs by Aid of Lucas Sequences
Lucas Tests for Mersenne Numbers
A Relaxation of Theorem 4.8
Pocklington’s Theorem
Lehmer-Pocklington’s Theorem
Pocklington-Type Theorems for Lucas Sequences
Primality Tests for Integers of the form Ν = h·2n−1, when 3∤h
Primality Tests for N=h·2n−1, when 3|h
The Combined Ν−1 and Ν+1 Test
Lucas Pseudoprimes
Modern Pnmality Proofs
The Jacobi Sum Pnmality Test
Three Lemmas
Lenstra’s Theorem
The Sets Ρ and Q
Running Time for the APRCL Test
Elliptic Curve Pnmality Proving, ECPP
The Goldwasser-Kilian Test
Atkin’s TestClassical Methods of FactorizationWhen Do We Attempt Factorization?
Trial Division
A Computer Implementation of Trial Division
Euclid’s Algorithm as an Aid to Factorization
Fermat’s Factoring Method
Legendre’s Congruence
Euler’s Factoring Method
Gauss’ Factoring Method
Legendre’s Factoring Method
The Number of Prime Factors of Large Numbers
How Does a Typical Factorization Look?
The Erdős-Kac Theorem
The Distribution of Prime Factors of Various Sizes
Dickman’s Version of Theorem 5.4
A More Detailed Theory
The Size of the kth Largest Prime Factor of Ν
Smooth Integers
Searching for Factors of Certain Forms
Legendre’s Theorem for the Factors of Ν = aⁿ ± bⁿ
Adaptation to Search for Factors of the Form p = 2kn+1
Adaptation of Trial Division
Adaptation of Fermat’s Factoring Method
Adaptation of Euclid’s Algorithm as an Aid to FactorizationModern Factorization MethodsChoice of Method
Pollard’s (p−1)-Method
Phase 2 of the (p−1)-Method
The (p+1)-Method
Pollard’s rho Method
A Computer Program for Pollard’s rho Method
An Algebraic Description of Pollard’s rho Method
Brent’s Modification of Pollard’s rho Method
The Pollard-Brent Method for p = 2kn + 1
Shanks’ Factoring Method SQUFOF
A Computer Program for SQUFOF
Comparison Between Pollard’s rho Method and SQUFOF
Morrison and Brillhart’s Continued Fraction Method CFRAC
The Factor Base
An Example of a Factorization with CFRAC
Further Details of CFRAC
The Early Abort Strategy
Results Achieved with CFRAC
Running Time Analysis of CFRAC
The Quadratic Sieve, QS
Smallest Solutions to Q(x) = 0 mod p
Special Factors
Results Achieved with QS
The Multiple Polynomial Quadratic Sieve, MPQS
Results Achieved with MPQS
Running Time Analysis of QS and MPQS
The Schnorr-Lenstra Method
Two Categories of Factorization Methods
Lenstra’s Elliptic Curve Method, ECM
Phase 2 of ECM
The Choice of A, B, and P₁
Running Times of ECM
Recent Results Achieved with ECM
The Number Field Sieve, NFS
Factoring Both in Ζ and in Z(z)
A Numerical Example
The General Number Field Sieve, GNFS
Running Times of NFS and GNFS
Results Achieved with NFS. Factorization of F₉
Strategies in Factoring
How Fast Can a Factorization Algorithm Be?Prime Numbers and Cryptography
Practical Secrecy
Keys in Cryptography
Arithmetical Formulation
RSA Cryptosystems
How to Find the Recovery Exponent
A Worked Example
Selecting Keys
Finding Suitable Primes
The Fixed Points of an RSA System
How Safe is an RSA Cryptosystem?
Superior FactorizationAppendix 1 Basic Concepts in Higher AlgebraModules
Euclid’s Algorithm
The Labor Involved in Euclid’s Algorithm
A Definition Taken from the Theory of Algorithms
A Computer Program for Euclid’s Algorithm
Reducing the Labor
Binary Form of Euclid’s Algorithm
The Diophantine Equation ax+by = c
Groups
Lagrange’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 CharactersAppendix 2 Basic Concepts in Higher Arithmetic
Divisors. Common Divisors
The Fundamental Theorem of Arithmetic
Congruences
Linear Congruences
Linear Congruences and Euclid’s Algorithm
Systems of Linear Congruences
The Residue Classes mod p Constitute a Field
The Primitive Residue Classes mod p
The Structure of the Group M_n
Homomorphisms of M_q when q is a Prime
Carmichael’s Function
Carmichael’s TheoremAppendix 3 Quadratic Residues
Legendre’s Symbol
Arithmetic Rules for Residues and Non-Residues
Euler’s Criterion for the Computation of (a/p)
The Law of Quadratic Reciprocity
Jacobi’s Symbol
A PASCAL Function for Computing (a/n)
The Quadratic Congruence x² ≡ c mod p
The Case p = 4k + 1Appendix 4 The Arithmetic of Quadratic Fields
Integers of Q(√D)
Units of Q(√D)
Associated Numbers in Q(√D)
Divisibility in Q(√D)
Fermat’s Theorem in Q(√D)
Primes in Q(√D)
Factorization of Integers in Q(√D)Appendix 5 Higher Algebraic Number FieldsAlgebraic Numbers
Numbers in Q(z). The Ring Z(z) of Integers in Q(z)
The Norm in Q(z). Units of Q(z)
Divisibility and Primes in Z(z)
The Field Q(∛−2) and the Ring Z(∛−2)
Primes in Z(∛−2)Appendix 6 Algebraic FactorsFactorization of Polynomials
The Cyclotomic Polynomials
The Polynomial xⁿ + yⁿ
The Polynomial xⁿ + ayⁿ
Aurifeuillian Factorizations
Factorization Formulas
The Algebraic Structure of Aurifeuillian Numbers
A formula by Gauss for xⁿ − yⁿAppendix 7 Elliptic Curves
Cubics
Rational Points on Rational Cubics
Homogeneous Coordinates
Elliptic Curves
Rational Points on Elliptic CurvesAppendix 8 Continued FractionsWhat Is a Continued Fraction?
Regular Continued Fractions. Expansions
Evaluating a Continued Fraction
Continued Fractions as Approximations
Euclid’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-Length
Short Periods
Continued Fractions and Quadratic ResiduesAppendix 9 Multiple-Precision ArithmeticVarious 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
A Computer Program for Pollard’s rho MethodAppendix 10 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 PrimesAppendix 11Functions 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
ApplicationsTables. For Contents, see page 374
List of Textbooks
Index