A course in computational number theory / David Bressoud, Stan Wagon

This book is an introduction to elementary computational number theory. It is structured in nine chapters, and two appendices. Moreover, it is provided with a CD-ROM, which however requires Mathematica. Chapter one is a recall of fundamentals, like the Euclidean algorithm, modular arithmetic or fast powers. Chapter two is devoted to solving linear congruences, and treats pseudoprimes as well. Chapter three concerns mainly Euler's ϕ function and primitive roots for primes. Chapter four treats prime numbers, in particular prime testing and certification. Some applications, like the RSA cryptosystem, are described in Chapter five. Chapter six speaks about quadratic residues and provides a proof of the quadratic reciprocity law. Continued fractions are the heart of Chapter seven. The applications to prime testing of Lucas sequences is presented in Chapter eight. Chapter nine concerns Gaussian numbers and the problem of the decomposition of primes in sums of two squares. Appendix A is an introduction to Mathematica, and finally appendix B provides a proof that Lucas certificates exist. (Zentralblatt)

Bibliogr. p. [355]-357. Index