Prime numbers and computer methods for factorization (Q5902990)

This is one of the very first books completely devoted to computational number theory, a branch of number theory which has attracted much attention since the advent of electronic computers. The book centers around: prime numbers and their distribution; how to recognize a given number to be prime; if it is not prime, how to find the prime numbers which compose this number; how prime numbers may play a role in cryptography. This book is an extremely practical one: if you start reading somewhere (which is easy because the various chapters may be read independently), and if you have access to some computing equipment, then there is a good chance that, after less than half an hour, you find yourself programming your computer in order to answer one of the many questions, to check or extend one of the many examples, or to practice one of the exercises which are scattered around in the book. At least the reviewer could not resist the temptation to do so many times, and this, unfortunately, caused quite a delay in the completion of this book's review. The reviewer is tempted to advise the interested reader to buy two copies of this book: one for your office and one for your home desk. This removes the need to carry this book to and fro betweem office and home. Apart from the wealth of practicing material, the book also contains many worked-out examples programmed in PASCAL, and excellent means to describe the details of the algorithms treated in this book. Chapter 1 is concerned with the numer of primes below a given limit, and with various methods to compute this function. Chapter 2 treats the asymptotic behaviour of the prime counting function and its approximation by more simple functions, and the relation of the prime numbers with the Riemann zeta-function and its complex zeros. In chapter 3, finer details of the distribution of the primes are studied, like gaps between primes, clusters of primes and primes in arithmetic progressions. Almost nothing is proved but many conjectures are mentioned. Chapter 4 describes many methods which may help to recognize whether a given number is prime or not. Here the important distinction is made between numbers of a special form (like the Mersenne numbers) and general numbers. As a striking example, the author describes how A. Ferrier, in 1951, proved primality of \(N=(2^{148}+1)/17\) (a 45 decimal digit number), by using information about the factorization of N- 1. This chapter also describes into some detail the recent primality proving algorithm based on ideas of Adleman, Pomerance, Rumely, Cohen and Lenstra, which has nearly polynomial running time, and by which it is possible now to prove primality of up to 200 decimal digit numbers in a reasonable time on a modern fast computer. (The implementation of this algorithm has been documented in: \textit{H. Cohen} and \textit{A. K. Lenstra}, Implementation of a new primality test, Report CS-R8505, Centre for Mathematics and Computer Science, Kruislaan 413, 1098 SK, Amsterdam, The Netherlands.) Chapter 5 gives an extensive treatment of the many known factorization methods, including the most powerful methods which are based on combining congruences modulo N (where N is the number to be factorized) into a congruence of the form \(X^ 2 = Y^ 2 (mod N)\), which, if \(X\not\equiv \pm Y (mod N)\), produces a factor of N. The running time of these congruence methods depends on the size of the number N and not on its composing prime factors. Shortly after the appearance of this book the so-called elliptic curve method (ecm) of H. W. Lenstra jun. came to be known, and its practical performance is very promising. Ecm has a running time which depends on the size of the one but largest prime factor in the number to be factorized. (The ecm has been described in the paper of \textit{H. W. Lenstra} jun., Factoring integers with elliptic curves, preprint, Math. Institute, Univ. of Amsterdam, Roetersstraat 15, 1018 WB Amsterdam, The Netherlands). Chapter 6, finally, describes the role that is played by difficult-to- factorize numbers in cryptography in so-called public key cryptosystems, which were devised by Rivest, Shamir and Adleman. - Chapter 1 to 6 comprise 236 pages. The next part (130 pages) is devoted to a description of background material, frequently referred to in Chapters 1 to 6. It describes a number of basic concepts in higher algebra (modules, groups, rings, field, group characters), basic concepts in higher arithmetic (congruences, solution of linear congruences, primitive residue classes), quadratic residues, quadratic fields, continued fractions, algebraic factors, numbers of a special form, multi-precision arithmetic, fast multiplication of large integers, and Riemann-Stieltjes integration. The large amount of material compressed in these 130 pages make them suitable as a means to fresh up memory, rather than as a means to a first acquaintance. The book closes with an interesting collection of tables which are suitable in computational number theory (the primes below 12553, primes between \(10^ n\) and \(10^ n+1000\), the number of primes below a given number, factors of Fermat numbers, primes of the form \(h\cdot 2^ n\pm 1\), factors of Mersenne numbers, factors of many types of numbers of the form \(a^ n\pm b^ n\), quadratic residues and, finally, Gauss' and Lucas' formulas for cyclotomic polynomials). The book is very carefully prepared and the reviewer has found only one error: on page 268, line 4 from above one should read 8991(-y) rather than 8991y. A few other critical remarks: in Appendix I, page 248, line 17, it is not clear why the subgroup is abelian; on page 258, line 1, the concept of a generator of a cyclic group is used without being defined before; in Appendix 5, page 302, the first few partial denominators of the regular continued fraction of e are computed by repeating the process of taking the integral part and inverting the fractional part; the conclusion that ''This computation produces the famous expansion of e'' should have been attended with the warning that accuracy is lost in the course of this process.