Elementary Number Theory: Primes, Congruences, and Secrets a Computational Approach

Contents......Page 8
Preface......Page 10
1. Prime Numbers......Page 12
1.1 Prime Factorization......Page 13
1.2 The Sequence of Prime Numbers......Page 21
1.3 Exercises......Page 30
2. The Ring of Integers Modulo n......Page 32
2.1 Congruences Modulo n......Page 33
2.2 The Chinese Remainder Theorem......Page 40
2.3 Quickly Computing Inverses and Huge Powers......Page 42
2.4 Primality Testing......Page 47
2.5 The Structure of (Z/pZ)[sup(*)]......Page 50
2.6 Exercises......Page 55
3.1 Playing with Fire......Page 60
3.2 The Diffie-Hellman Key Exchange......Page 62
3.3 The RSA Cryptosystem......Page 67
3.4 Attacking RSA......Page 72
3.5 Exercises......Page 78
4. Quadratic Reciprocity......Page 80
4.1 Statement of the Quadratic Reciprocity Law......Page 81
4.2 Euler\'s Criterion......Page 84
4.3 First Proof of Quadratic Reciprocity......Page 86
4.4 A Proof of Quadratic Reciprocity Using Gauss Sums......Page 92
4.5 Finding Square Roots......Page 97
4.6 Exercises......Page 100
5. Continued Fractions......Page 104
5.1 The Definition......Page 105
5.2 Finite Continued Fractions......Page 106
5.3 Infinite Continued Fractions......Page 112
5.4 The Continued Fraction of e......Page 118
5.5 Quadratic Irrationals......Page 121
5.6 Recognizing Rational Numbers......Page 126
5.7 Sums of Two Squares......Page 128
5.8 Exercises......Page 132
6. Elliptic Curves......Page 134
6.1 The Definition......Page 135
6.2 The Group Structure on an Elliptic Curve......Page 136
6.3 Integer Factorization Using Elliptic Curves......Page 140
6.4 Elliptic Curve Cryptography......Page 146
6.5 Elliptic Curves Over the Rational Numbers......Page 151
6.6 Exercises......Page 157
Answers and Hints......Page 160
References......Page 166
C......Page 172
E......Page 173
L......Page 174
P......Page 175
T......Page 176
Z......Page 177