A Computational Approach

**William Stein**

**Date:** March 2007

To my wife Clarita Lefthand.

- Contents
- Preface
- Prime Numbers

- The Ring of Integers Modulo
- Congruences Modulo
- The Chinese Remainder Theorem
- Quickly Computing Inverses and Huge Powers
- Primality Testing
- The Structure of
- Exercises

- Public-Key Cryptography

- Quadratic Reciprocity
- Statement of the Quadratic Reciprocity Law
- Euler's Criterion
- First Proof of Quadratic Reciprocity
- A Proof of Quadratic Reciprocity Using Gauss Sums
- Finding Square Roots
- Exercises

- Continued Fractions
- Finite Continued Fractions
- Infinite Continued Fractions
- The Continued Fraction of
- Quadratic Irrationals
- 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
- Elliptic Curve Cryptography
- Elliptic Curves Over the Rational Numbers
- Exercises

- Answers and Hints
- Bibliography
- Index
- About this document ...

William 2007-06-01