Elementary number theory and elliptic curves (web draft, Sept. 2004)

Stein W.

Table of contents :
Preface……Page 6
Prime Factorization……Page 8
The Sequence of Prime Numbers……Page 16
Exercises……Page 22
Congruences Modulo n……Page 24
The Chinese Remainder Theorem……Page 30
Quickly Computing Inverses and Huge Powers……Page 32
Finding Primes……Page 36
The Structure of (Z/pZ)*……Page 37
Exercises……Page 41
Public-Key Cryptography……Page 46
The Diffie-Hellman Key Exchange……Page 49
The RSA Cryptosystem……Page 54
Attacking RSA……Page 57
Exercises……Page 61
Quadratic Reciprocity……Page 62
Statement of the Quadratic Reciprocity Law……Page 63
Euler’s Criterion……Page 65
First Proof of Quadratic Reciprocity……Page 66
A Proof of Quadratic Reciprocity Using Gauss Sums……Page 71
Finding Square Roots……Page 75
Exercises……Page 77
Continued Fractions……Page 80
Finite Continued Fractions……Page 81
Infinite Continued Fractions……Page 86
The Continued Fraction of e……Page 91
Quadratic Irrationals……Page 94
Recognizing Rational Numbers……Page 99
Sums of Two Squares……Page 100
Exercises……Page 103
Elliptic Curves……Page 106
The Group Structure on an Elliptic Curve……Page 107
Integer Factorization Using Elliptic Curves……Page 110
Elliptic Curve Cryptography……Page 115
Elliptic Curves Over the Rational Numbers……Page 119
Exercises……Page 124
Computational Number Theory……Page 126
Prime Numbers……Page 128
The Ring of Integers Modulo n……Page 134
Public-Key Cryptography……Page 142
Quadratic Reciprocity……Page 148
Continued Fractions……Page 151
Elliptic Curves……Page 155
Exercises……Page 168
Answers and Hints……Page 170
References……Page 178