文档介绍：This is page i
Printer: Opaque this
Elementary Number Theory
William Stein
September 2004
ii
To my students and my wife, Clarita Lefthand.
This is page iii
Printer: Opaque this
Contents
Preface 3
1 Prime Numbers 5
Prime Factorization . . . . . . . . . . . . . . . . . . . . . . 5
The Sequence of Prime Numbers . . . . . . . . . . . . . . . 13
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2 The Ring of Integers Modulo n 21
Congruences Modulo n . . . . . . . . . . . . . . . . . . . . . 21
The Chinese Remainder Theorem . . . . . . . . . . . . . . . 27
puting Inverses and Huge Powers . . . . . . . . 29
Finding Primes . . . . . . . . . . . . . . . . . . . . . . . . . 33
The Structure of (Z/pZ)∗. . . . . . . . . . . . . . . . . . . 34
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3 Public-Key Cryptography 43
The Diffie-Hellman Key Exchange . . . . . . . . . . . . . . 46
The RSA Cryptosystem . . . . . . . . . . . . . . . . . . . . 51
Attacking RSA . . . . . . . . . . . . . . . . . . . . . . . . . 54
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
4 Quadratic Reciprocity 59
Statement of the Quadratic Reciprocity Law . . . . . . . . 60
Euler’s Criterion . . . . . . . . . . . . . . . . . . . . . . . . 62
Contents 1
First Proof of Quadratic Reciprocity . . . . . . . . . . . . . 63
A Proof of Quadratic Reciprocity Using Gauss Sums . . . . 68
Finding Square Roots . . . . . . . . . . . . . . . . . . . . . 72
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
5 Continued Fractions 77
Finite Continued Fractions . . . . . . . . . . . . . . . . . . 78
Infinite Continued Fractions . . . . . . . . . . . . . . . . . . 83
The Continued Fraction of e . . . . . . . . . . . . . . . . . . 88
Quadratic Irrationals . . . . . . . . . . . . . . . . . . . . . .