A Course in Computational Number Theory (Textbooks in Mathematical Sciences)

"The book presents the standard curriculum of a first course in number theory: the fundamental theorem of arithmetic, congruences, Fermat's theorem and Euler's generalization, primitive roots, facts about the distribution of primes, quadratic residues, Pell's equation and sums of squares. The proofs are constructive and the emphasis is on computing. Algorithms are given for GCD, solving linear congruences, factoring, primality testing, finding large primes, evaluating Jacobi symbols, computing square roots modulo a prime, finding continued fractions of quadratic irrationals, solving Pell's equation and expressing an integer as the sum of two squares. The diverse applications include repeating decimals, the RSA cipher, digital signatures, the Yao millionaire problem, check digits, the cattle problem of Archimedes and the crystal structure of salt. There is an excellent survey of many (probable) prime tests with Lucas sequences. The computer algebra system Mathematica is used throughout the book and summarized in an appendix. On nearly every page, Mathematica instructions illustrate algorithms and provide examples. An accompanying CD-ROM holds a rich assortment of Mathematica programs from the text. Three color plates display the power residues modulo small primes and the Gaussian primes reachable from $1+i$ in steps of bounded length."--MATHEMATICAL REVIEWS