Enhanced descriptions from Syndetics:

Numbers are part of our everyday experience and their properties have fascinated mankind since ancient times. Deciding whether a number is prime and if not, what its factors are, are both fundamental problems. In recent years analysis and solution of these problems have assumed commercial significance since large primes are an essential feature of secure methods of information transmission. The purely mathematical fascination that led to the development of methods for primality testing has been supplemented by the need to test within reasonable timescales, and computational methods have entered at all levels of number theory. In this book, Peter Giblin describes, in the context of an introduction to the theory of numbers, some of the more elementary methods for factorization and primality testing; that is, methods independent of a knowledge of other areas of mathematics. Indeed everything is developed from scratch so the mathematical prerequisites are minimal. An essential feature of the book is the large number of computer programs (written in Pascal) and a wealth of computational exercises and projects (in addition to more usual theory exercises). The theoretical development includes continued fractions and quadratic residues, directed always towards the two fundamental problems of primality testing and factorization. There is time, all the same, to include a number of topics and projects of a purely 'recreational' nature.

Table of contents provided by Syndetics

• Preface (p. vii)
• Logical dependence of chapters (p. xi)
• 1. The Fundamental Theorem, Greatest Common Divisors and Least Common Multiples (p. 1)
• 1. Primes and the fundamental theorem (p. 1)
• 2. Greatest common divisor and least common multiple (p. 7)
• 3. Euclid's algorithm for the gcd (p. 12)
• 4. [x] and applications (p. 24)
• 5. Further projects (p. 29)
• 2. Listing Primes (p. 37)
• 1. Primes by division (p. 37)
• 2. Primes by multiplication (elimination of composites) (p. 50)
• 3. Approximations to [pi](x) (p. 52)
• 4. The sieve of Eratosthenes (p. 55)
• 3. Congruences (p. 69)
• 1. Congruences: basic properties (p. 69)
• 2. Inverses mod m and solutions of certain congruences (p. 74)
• 3. Further examples of congruences (p. 81)
• 4. Powers and Pseudoprimes (p. 86)
• 1. Fermat's (little) theorem (p. 86)
• 2. The power algorithm (p. 89)
• 3. Head's algorithm for multiplication mod m (p. 93)
• 4. Pseudoprimes (p. 98)
• 5. Wilson's theorem (p. 102)
• 5. Miller's Test and Strong Pseudoprimes (p. 104)
• 1. Miller's test (p. 104)
• 2. Probabilistic primality testing (p. 109)
• 6. Euler's Theorem, Orders and Primality Testing (p. 112)
• 1. Euler's function (the [phis]-function or totient function) (p. 112)
• 2. Euler's theorem and the concept of order (p. 119)
• 3. Primality tests (p. 124)
• 4. Periods of decimals (p. 130)
• 7. Cryptography (p. 133)
• 1. Exponentiation ciphers (p. 134)
• 2. Public key cryptography: RSA ciphers (p. 136)
• 3. Coin-tossing by telephone (p. 145)
• 8. Primitive Roots (p. 147)
• 1. Properties and applications of primitive roots (p. 147)
• 2. Existence and nonexistence of primitive roots (p. 149)
• 9. The Number of Divisors d and the Sum of Divisors [sigma] (p. 158)
• 1. The function d(n) (p. 158)
• 2. Multiplicative functions and the sum function [sigma](n) (p. 162)
• 3. Tests for primality of the Mersenne numbers 2[superscript m] - 1 (p. 170)
• 10. Continued Fractions and Factoring (p. 174)
• 1. Continued fractions: initial ideas and definitions (p. 175)
• 2. The continued fraction for [square root]n (p. 180)
• 3. Proofs of some properties of continued fractions (p. 186)
• 4. Pell's equation (p. 189)
• 5. The continued fraction factoring method (p. 191)
• 11. Quadratic Residues (p. 200)
• 1. Definitions and examples (p. 200)
• 2. The quadratic character of 2 (p. 203)
• 3. Quadratic reciprocity (p. 206)
• 4. The Jacobi symbol and a program for finding (n/p) (p. 211)
• 5. Solving the equation x[superscript 2] [identical with] a (mod p): quadratic congruences (p. 217)
• Bibliography (p. 225)
• Index (p. 231)
• Index of Listed Programs (p. 236)
• Index of Notation (p. 237)

Reviews provided by Syndetics

CHOICE Review

Two notable trends come together here: first, certain parts of number theory have lately entered the sphere of applied mathematics, most notable for their use in cryptography; second, ever more practically minded undergraduates are increasingly resistant to purely theoretical pursuits. Cryptographers are most interested in algorithms for primality testing and factorization, and in recent years many of these have been cleverly spun out of well-known theorems of elementary number theory. Indeed, the core material in this book is surprisingly similar to that found in some of the easier traditional elementary number theory books (e.g., H. Davenport, The Higher Arithmetic, 6th ed., 1992), while topics such as elliptic curves, the basis of many important new algorithms, are not mentioned. A serious omission is some development of the basic notions of computational complexity (e.g., polynomial time) so that the reader might analyze the efficiency of the various algorithms or the difficulty of the various computational problems. Listings of Pascal programs (Mathematica, offering unlimited precision, would have been a more useful choice) to implement various algorithms take up a number of pages; such programs are better distributed on floppy disk The reader may have trouble discerning the broad outlines of modern number theory and choosing a direction for further study. Upper-division undergraduate.