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

✍ Scribed by William Stein

• Publisher: Springer
• Year: 2010
• Tongue: English
• Leaves: 172
• Edition: online edition (172p., 16. November 2011)
• Category: Library

✦ Synopsis

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

Preface......Page 6
Prime Numbers......Page 8
Prime Factorization......Page 9
The Sequence of Prime Numbers......Page 17
Exercises......Page 26
The Ring of Integers Modulo n......Page 28
Congruences Modulo n......Page 29
The Chinese Remainder Theorem......Page 36
Quickly Computing Inverses and Huge Powers......Page 38
Primality Testing......Page 43
The Structure of (Z/pZ)*......Page 46
Exercises......Page 51
Playing with Fire......Page 56
The Diffie-Hellman Key Exchange......Page 58
The RSA Cryptosystem......Page 63
Attacking RSA......Page 68
Exercises......Page 74
Quadratic Reciprocity......Page 76
Statement of the Quadratic Reciprocity Law......Page 77
Euler's Criterion......Page 80
First Proof of Quadratic Reciprocity......Page 82
A Proof of Quadratic Reciprocity Using Gauss Sums......Page 88
Finding Square Roots......Page 93
Exercises......Page 96
Continued Fractions......Page 100
The Definition......Page 101
Finite Continued Fractions......Page 102
Infinite Continued Fractions......Page 108
The Continued Fraction of e......Page 114
Quadratic Irrationals......Page 117
Recognizing Rational Numbers......Page 122
Sums of Two Squares......Page 124
Exercises......Page 128
Elliptic Curves......Page 130
The Definition......Page 131
The Group Structure on an Elliptic Curve......Page 132
Integer Factorization Using Elliptic Curves......Page 136
Elliptic Curve Cryptography......Page 142
Elliptic Curves Over the Rational Numbers......Page 147
Exercises......Page 153
Answers and Hints......Page 156
References......Page 162
Index......Page 167