Elementary Number Theory. Primes, Congruences and Secrets

Cover.pdf......Page 1
front-matter.pdf......Page 3
Preface......Page 10
Prime Numbers......Page 12
Prime Factorization......Page 13
The Sequence of Prime Numbers......Page 21
Exercises......Page 30
The Ring of Integers Modulo n......Page 32
Congruences Modulo n......Page 33
The Chinese Remainder Theorem......Page 40
Quickly Computing Inverses and Huge Powers......Page 42
Primality Testing......Page 47
The Structure of (Z/pZ)*......Page 50
Exercises......Page 55
Playing with Fire......Page 59
The Diffie-Hellman Key Exchange......Page 61
The RSA Cryptosystem......Page 66
Attacking RSA......Page 71
Exercises......Page 77
Quadratic Reciprocity......Page 79
Statement of the Quadratic Reciprocity Law......Page 80
Euler's Criterion......Page 83
First Proof of Quadratic Reciprocity......Page 85
A Proof of Quadratic Reciprocity Using Gauss Sums......Page 91
Finding Square Roots......Page 96
Exercises......Page 99
Continued Fractions......Page 102
The Definition......Page 103
Finite Continued Fractions......Page 104
Infinite Continued Fractions......Page 110
The Continued Fraction of e......Page 116
Quadratic Irrationals......Page 119
Recognizing Rational Numbers......Page 124
Sums of Two Squares......Page 126
Exercises......Page 130
Elliptic Curves......Page 132
The Definition......Page 133
The Group Structure on an Elliptic Curve......Page 134
Integer Factorization Using Elliptic Curves......Page 138
Elliptic Curve Cryptography......Page 144
Elliptic Curves Over the Rational Numbers......Page 149
Exercises......Page 155
Answers and Hints......Page 157
Index......Page 163