1st Edition

An Introduction to Number Theory with Cryptography

By James Kraft, Lawrence C. Washington Copyright 2014
    572 Pages 18 B/W Illustrations
    by Chapman & Hall

    Number theory has a rich history. For many years it was one of the purest areas of pure mathematics, studied because of the intellectual fascination with properties of integers. More recently, it has been an area that also has important applications to subjects such as cryptography. An Introduction to Number Theory with Cryptography presents number theory along with many interesting applications. Designed for an undergraduate-level course, it covers standard number theory topics and gives instructors the option of integrating several other topics into their coverage. The "Check Your Understanding" problems aid in learning the basics, and there are numerous exercises, projects, and computer explorations of varying levels of difficulty.

    Introduction
    Diophantine Equations
    Modular Arithmetic
    Primes and the Distribution of Primes
    Cryptography

    Divisibility
    Divisibility
    Euclid's Theorem
    Euclid's Original Proof
    The Sieve of Eratosthenes
    The Division Algorithm
    The Greatest Common Divisor
    The Euclidean Algorithm
    Other Bases
    Linear Diophantine Equations
    The Postage Stamp Problem
    Fermat and Mersenne Numbers
    Chapter Highlights
    Problems

    Unique Factorization
    Preliminary Results
    The Fundamental Theorem of Arithmetic
    Euclid and the Fundamental Theorem of Arithmetic
    Chapter Highlights
    Problems

    Applications of Unique Factorization
    A Puzzle
    Irrationality Proofs
    The Rational Root Theorem
    Pythagorean Triples
    Differences of Squares
    Prime Factorization of Factorials
    The Riemann Zeta Function
    Chapter Highlights
    Problems

    Congruences
    Definitions and Examples
    Modular Exponentiation
    Divisibility Tests
    Linear Congruences
    The Chinese Remainder Theorem
    Fractions mod m
    Fermat's Theorem
    Euler's Theorem
    Wilson's Theorem
    Queens on a Chessboard
    Chapter Highlights
    Problems

    Cryptographic Applications
    Introduction
    Shift and Affine Ciphers
    Secret Sharing
    RSA
    Chapter Highlights
    Problems

    Polynomial Congruences
    Polynomials Mod Primes
    Solutions Modulo Prime Powers
    Composite Moduli
    Chapter Highlights
    Problems

    Order and Primitive Roots
    Orders of Elements
    Primitive Roots
    Decimals
    Card Shuffling
    The Discrete Log Problem
    Existence of Primitive Roots
    Chapter Highlights
    Problems

    More Cryptographic Applications
    Diffie-Hellman Key Exchange
    Coin Flipping over the Telephone
    Mental Poker
    The ElGamal Public Key Cryptosystem
    Digital Signatures
    Chapter Highlights
    Problems

    Quadratic Reciprocity
    Squares and Square Roots Mod Primes
    Computing Square Roots Mod p
    Quadratic Equations
    The Jacobi Symbol
    Proof of Quadratic Reciprocity
    Chapter Highlights
    Problems

    Primality and Factorization
    Trial Division and Fermat Factorization
    Primality Testing Factorization
    Coin Flipping over the Telephone
    Chapter Highlights
    Problems

    Geometry of Numbers
    Volumes and Minkowski's Theorem
    Sums of Two Squares
    Sums of Four Squares
    Pell's Equation
    Chapter Highlights
    Problems

    Arithmetic Functions
    Perfect Numbers
    Multiplicative Functions
    Chapter Highlights
    Problems

    Continued Fractions
    Rational Approximations; Pell's Equation
    Basic Theory
    Rational Numbers
    Periodic Continued Fractions
    Square Roots of Integers
    Some Irrational Numbers
    Chapter Highlights
    Problems

    Gaussian Integers
    Complex Arithmetic
    Gaussian Irreducibles
    The Division Algorithm
    Unique Factorization
    Applications
    Chapter Highlights
    Problems

    Algebraic Integers
    Quadratic Fields and Algebraic Integers
    Units
    Z[√-2]
    Z[√3]
    Non-unique Factorization
    Chapter Highlights
    Problems

    Analytic Methods
    Σ1/p Diverges
    Bertrand's Postulate
    Chebyshev's Approximate Prime Number Theorem
    Chapter Highlights
    Problems

    Epilogue: Fermat's Last Theorem
    Introduction
    Elliptic Curves
    Modularity

    Supplementary Topics
    Geometric Series
    Mathematical Induction
    Pascal’s Triangle and the Binomial Theorem
    Fibonacci Numbers
    Problems

    Answers and Hints for Odd-Numbered Exercises
    Index

    Biography

    James S. Kraft, Lawrence C. Washington

    "… provides a fine history of number theory and surveys its applications. College-level undergrads will appreciate the number theory topics, arranged in a format suitable for any standard course in the topic, and will also appreciate the inclusion of many exercises and projects to support all the theory provided. In providing a foundation text with step-by-step analysis, examples, and exercises, this is a top teaching tool recommended for any cryptography student or instructor."
    —California Bookwatch, January 2014