Contents

• Prime Numbers
  • Prime Factorization
    • Primes
    • The Greatest Common Divisor
    • Numbers Factor as Products of Primes
    • The Fundamental Theorem of Arithmetic
  • The Sequence of Prime Numbers
    • There Are Infinitely Many Primes
    • Enumerating Primes
    • The Largest Known Prime
    • Primes of the Form $ax+b$
    • How Many Primes are There?
  • Exercises
  
  
• The Ring of Integers Modulo $n$
  • Congruences Modulo $n$
    • Linear Equations Modulo $n$
    • Fermat's Little Theorem
    • Wilson's Theorem
  • The Chinese Remainder Theorem
    • Multiplicative Functions
  • Quickly Computing Inverses and Huge Powers
    • How to Solve $ax\equiv 1\pmod{n}$
    • How to Compute $a^m\pmod{n}$
  • Primality Testing
  • The Structure of $(\mathbb{Z}/p\mathbb{Z}{})^*$
    • Polynomials over $\mathbb{Z}/p\mathbb{Z}{}$
    • Existence of Primitive Roots
    • Artin's Conjecture
    • Computing Primitive Roots
  • Exercises
  
  
• Public-Key Cryptography
  • The Diffie-Hellman Key Exchange
    • The Discrete Log Problem
    • Realistic Diffie-Hellman Example
    • The Man in the Middle Attack
  • The RSA Cryptosystem
    • How RSA works
    • Encoding a Phrase in a Number
    • Some Complete Examples
  • Attacking RSA
    • Factoring $n$ Given $\varphi (n)$
    • When $p$ and $q$ are Close
    • Factoring $n$ Given $d$
    • Further Remarks
  • Exercises
  
  
• Quadratic Reciprocity
  • Statement of the Quadratic Reciprocity Law
  • Euler's Criterion
  • First Proof of Quadratic Reciprocity
    • Euler's Proposition
    • Proof of Quadratic Reciprocity
  • A Proof of Quadratic Reciprocity Using Gauss Sums
    • Proof of Quadratic Reciprocity
  • Finding Square Roots
  • Exercises
  
  
• Continued Fractions
  • Finite Continued Fractions
    • Partial Convergents
    • The Sequence of Partial Convergents
    • Every Rational Number is Represented
  • Infinite Continued Fractions
    • The Continued Fraction Procedure
    • Convergence of Infinite Continued Fractions
  • The Continued Fraction of $e$
    • Preliminaries
    • Two Integral Sequences
    • A Related Sequence of Integrals
    • Extensions of the Argument
  • Quadratic Irrationals
    • Periodic Continued Fractions
    • Continued Fractions of Algebraic Numbers of Higher Degree
  • Recognizing Rational Numbers From Their Decimal Expansion
  • Sums of Two Squares
  • Exercises
  
  
• Elliptic Curves
  • The Definition
  • The Group Structure on an Elliptic Curve
  • Integer Factorization Using Elliptic Curves
    • Pollard's $(p-1)$ -Method
    • Motivation for the Elliptic Curve Method
    • Lenstra's Elliptic Curve Factorization Method
    • Examples
    • A Heuristic Explanation
  • Elliptic Curve Cryptography
    • Elliptic Curve Analogues of Diffie-Hellman
    • The ElGamal Cryptosystem and Digital Rights Management
    • The Elliptic Curve Discrete Logarithm Problem
  • Elliptic Curves Over the Rational Numbers
    • The Torsion Subgroup of $E(\mathbb{Q})$ and the Rank
    • The Congruent Number Problem
  • Exercises
  
  
• Bibliography
• Index