Elementary number theory: Primes, congruences, and secrets: A computational approach

William Stein9780387855240, 9780387855257, 0387855246, 0387855254

This is a textbook about classical elementary number theory and elliptic curves. The first part discusses elementary topics such as primes, factorization, continued fractions, and quadratic forms, in the context of cryptography, computation, and deep open research problems. The second part is about elliptic curves, their applications to algorithmic problems, and their connections with problems in number theory such as Fermat’s Last Theorem, the Congruent Number Problem, and the Conjecture of Birch and Swinnerton-Dyer. The intended audience of this book is an undergraduate with some familiarity with basic abstract algebra, e.g. rings, fields, and finite abelian groups.

---

Table of contents :
Cover.pdf……Page 1
front-matter.pdf……Page 2
Preface……Page 9
Prime Numbers……Page 11
Prime Factorization……Page 12
The Sequence of Prime Numbers……Page 20
Exercises……Page 29
The Ring of Integers Modulo n……Page 31
Congruences Modulo n……Page 32
The Chinese Remainder Theorem……Page 39
Quickly Computing Inverses and Huge Powers……Page 41
Primality Testing……Page 46
The Structure of (Z/pZ)*……Page 49
Exercises……Page 54
Playing with Fire……Page 58
The Diffie-Hellman Key Exchange……Page 60
The RSA Cryptosystem……Page 65
Attacking RSA……Page 70
Exercises……Page 76
Quadratic Reciprocity……Page 78
Statement of the Quadratic Reciprocity Law……Page 79
Euler’s Criterion……Page 82
First Proof of Quadratic Reciprocity……Page 84
A Proof of Quadratic Reciprocity Using Gauss Sums……Page 90
Finding Square Roots……Page 95
Exercises……Page 98
Continued Fractions……Page 101
The Definition……Page 102
Finite Continued Fractions……Page 103
Infinite Continued Fractions……Page 109
The Continued Fraction of e……Page 115
Quadratic Irrationals……Page 118
Recognizing Rational Numbers……Page 123
Sums of Two Squares……Page 125
Exercises……Page 129
Elliptic Curves……Page 131
The Definition……Page 132
The Group Structure on an Elliptic Curve……Page 133
Integer Factorization Using Elliptic Curves……Page 137
Elliptic Curve Cryptography……Page 143
Elliptic Curves Over the Rational Numbers……Page 148
Exercises……Page 154
Answers and Hints……Page 156
Index……Page 162