# An Introduction to Number Theory with Cryptography

## Preview

## Book Description

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.

## Table of Contents

**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

**Quadratic Fields and Algebraic Integers**

Algebraic Integers

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

## Reviews

"… 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