An Introduction to Number Theory with Cryptography

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.

IntroductionDiophantine EquationsModular ArithmeticPrimes and the Distribution of PrimesCryptographyDivisibilityDivisibilityEuclid's Theorem Euclid's Original Proof The Sieve of Eratosthenes The Division Algorithm The Greatest Common Divisor The Euclidean Algorithm Other BasesLinear Diophantine EquationsThe Postage Stamp Problem Fermat and Mersenne Numbers Chapter Highlights Problems Unique FactorizationPreliminary Results The Fundamental Theorem of Arithmetic Euclid and the Fundamental Theorem of ArithmeticChapter 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 CongruencesDefinitions and Examples Modular Exponentiation Divisibility TestsLinear Congruences The Chinese Remainder TheoremFractions mod m Fermat's Theorem Euler's Theorem Wilson's Theorem Queens on a Chessboard Chapter Highlights Problems Cryptographic ApplicationsIntroduction Shift and Affine Ciphers Secret Sharing RSA Chapter Highlights Problems Polynomial Congruences Polynomials Mod Primes Solutions Modulo Prime PowersComposite Moduli Chapter Highlights Problems Order and Primitive RootsOrders of Elements Primitive Roots DecimalsCard 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 NumbersVolumes and Minkowski's Theorem Sums of Two Squares Sums of Four Squares Pell's Equation Chapter Highlights Problems Arithmetic FunctionsPerfect Numbers Multiplicative Functions Chapter Highlights Problems Continued Fractions Rational Approximations; Pell's Equation Basic TheoryRational 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 IntegersQuadratic Fields and Algebraic IntegersUnits Z[v-2] Z[v3] Non-unique Factorization Chapter Highlights Problems Analytic MethodsS1/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 SeriesMathematical InductionPascal’s Triangle and the Binomial TheoremFibonacci NumbersProblems Answers and Hints for Odd-Numbered ExercisesIndex