Synopses & Reviews
"This is an excellent book for all students of mathematics, and no particular prerequisites are needed to be able to read it...This book is warmly recommended for everybody!' Elementa 'An excellent overview, with appropriate references. Includes Pascal programs, some exercises.' American Mathematical Monthly 'Riesel's outstanding technical monograph on recursive number theory and its numerous automated techniques has successfully passed a critical milestone: this is the second edition.' Computing Reviews 'The independent structure of each chapter of the book makes it 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.' Datenbank Mathematical Didactics Here is an outstanding technical monograph on recursive number theory and its numerous automated techniques. It successfully passes a critical milestone not allowed to many books, viz., a second edition...Many good things have happened to number theory during the past ten years since the first edition appeared and the author includes their highlights in great depth...All in all, this handy volume continues to be an attractive combination of number-theoretic precision, practicality, and theory with a rich blend of computer science.' Zbl. Math. This second edition is an introduction to applied number theory which meets the need for a text and reference book that is up-to-date and accessible to scientists and engineers as well as to the mathematically-inclined layman. This self-contained book will become required reading for students and researchers interested in cryptography and number theory. Series: Progress in Mathematics, Volume 126 "
Review
"Here is an outstanding technical monograph on recursive number theory and its numerous automated techniques. It successfully passes a critical milestone not allowed to many books, viz., a second edition. Many good things have happened to computational number theory during the ten years since the first edition appeared and the author includes their highlights in great depth. Several major sections have been rewritten and totally new sections have been added. The new material includes advances on applications of the elliptic curve method, uses of the number field sieve, and two new appendices on the basics of higher algebraic number fields and elliptic curves. Further, the table of prime factors of Fermat numbers has been significantly up-dated. ...Several other tables have been added so as to provide data to look for large prime factors of certain 'generalized' Fermat numbers, while several other tables on special numbers were simply deleted in the second edition. Still one can make several perplexing assertions or challenges: (1) prove that F\sb 5, F\sb 6, F\sb 7, F\sb 8 are the only four consecutive Fermat numbers which are bi-composite; (2) Show that F\sb{14} is bi- composite. (This accounts for the difficulty in finding a prime factor for it.) (3) What is the smallest Fermat quadri-composite?; and (4) Does there exist a Fermat number with an arbitrarily prescribed number of prime factors? All in all, this handy volume continues to be an attractive combination of number-theoretic precision, practicality, and theory with a rich blend of computer science." -Zentralblatt Math
Synopsis
1. The 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 Discussed.- 2. The Primes Viewed at Large.- No 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), pn, and ?(x).- The Number of Primes in Arithmetic Progressions.- 3. Subtleties 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 Conjecture.- 4. The Recognition of Primes.- Tests 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 N = 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 N = h - 2n ? 1, when 3?h.- Primality Tests for N = h - 2n ? 1, when 3?h.- The Combined N ? 1 and N + 1 Test.- Lucas Pseudoprimes.- Modern Primality Proofs.- The Jacobi Sum Primality Test.- Three Lemmas.- Lenstra's Theorem.- The Sets P and Q.- Running Time for the APRCL Test.- Elliptic Curve Primality Proving, ECPP.- The Goldwasser-Kilian Test.- Atkin's Test.- 5. Classical Methods of Factorization.- When Do We Attempt Factorization?.- Tri
Synopsis
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. 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.
Description
Includes bibliographical references (p. 457) and index.
Table of Contents
Preface.-The Number of Primes Below a Given Limit.-The Primes Viewed at Large.-Subtleties in the Distribution of Primes.-The Recognition of Primes.-Classical Methods of Factorization.-Modern Factorization Methods.-Prime Numbers and Cryptography.-Appendix 1. Basic Concepts in Higher Algebra.-Appendix 2. Basic concepts in Higher Arithmetic.-Appendix 3. Quadratic Residues.-Appendix 4. The Arithmetic of Quadratic Fields.-Appendix 5. Higher Algebraic Number Fields.-Appendix 6. Algebraic Factors.-Appendix 7. Elliptic Curves.-Appendix 8. Continued Fractions.-Appendix 9. Multiple-Precision Arithmetic.-Appendix 10. Fast Multiplication of Large Integers.-Appendix 11. The Stieltjes Integral.-Tables.-List of Textbooks.-Index.