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

The book is based on courses taught at Liverpool University and has been thoroughly class tested. The very concrete nature of the material and the constant interaction between theory and practice (that is, computing) appeal to students and provide an excellent context in which to learn both worthwhile mathematics and computer programming. 
Subject 
Numbers, Prime.


Factorization (Mathematics)

ISBN 
0521401828 (hbk.) 

0521409888 (paperback) 
