文档介绍：This is page i
Printer: Opaque this
Elementary Number Theory,
putational Approach
William Stein
March 2007
ii
To 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 . . . . . . . . . . . . . . . 14
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2 The Ring of Integers Modulo n 25
Congruences Modulo n . . . . . . . . . . . . . . . . . . . . . 25
The Chinese Remainder Theorem . . . . . . . . . . . . . . . 32
puting Inverses and Huge Powers . . . . . . . . 35
Primality Testing . . . . . . . . . . . . . . . . . . . . . . . . 40
The Structure of (Z/pZ)∗. . . . . . . . . . . . . . . . . . . 43
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3 Public-Key Cryptography 51
The Diffie-Hellman Key Exchange . . . . . . . . . . . . . . 54
The RSA Cryptosystem . . . . . . . . . . . . . . . . . . . . 60
Attacking RSA . . . . . . . . . . . . . . . . . . . . . . . . . 64
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
4 Quadratic Reciprocity 73
Statement of the Quadratic Reciprocity Law . . . . . . . . 74
Euler’s Criterion . . . . . . . . . . . . . . . . . . . . . . . . 77
Contents 1
First Proof of Quadratic Reciprocity . . . . . . . . . . . . . 79
A Proof of Quadratic Reciprocity Using Gauss Sums . . . . 85
Finding Square Roots . . . . . . . . . . . . . . . . . . . . . 90
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
5 Continued Fractions 95
Finite Continued Fractions . . . . . . . . . . . . . . . . . . 96
Infinite Continued Fractions . . . . . . . . . . . . . . . . . . 103
The Continued Fraction of e . . . . . . . . . . . . . . . . . . 109
Quadratic Irrationals . . . . . . . . . . . . . . . . . . .