Microchip Mathematics: Number Theory for Computer Users

COVER......Page 1
COPYRIGHT......Page 3
CONTENTS......Page 4
PREFACE......Page 6
O. BACKGROUND: PRIME NUMBERS......Page 10
1. Prime Numbers......Page 11
2. The Sieve of Eratosthenes......Page 13
3. The Distribution of Primes......Page 14
4. Largest Known Primes......Page 17
5. Conjectures About Primes......Page 18
Exercises 0......Page 20
Computer Problems 0......Page 21
1. Mathematical Induction......Page 23
2. Divisibility. The Euclidean Algorithm......Page 32
3. Efficiency of Algorithms. Multiprecision Arithmetic......Page 43
4. The Fibonnaci Sequence and the Efficiency of the Euclidean Algorithm......Page 52
5. Prime Numbers......Page 57
6. Diophantine Equations......Page 60
Exercises I......Page 64
Computer Problems I......Page 68
1. Congruence......Page 71
2. Modular Arithmetic......Page 86
3. Fermat's Little Theorem and the Euler Phi-Function......Page 103
4. Random Number Generators and Primitive Roots......Page 116
Exercises II......Page 137
Computer Problems II......Page 144
III. PRIMALITY TESTING AND FACTORISATION......Page 147
1. Perfect Numbers and Mersenne Primes......Page 148
2. Public Key Cryptography......Page 162
3. Primality Testing......Page 172
4. Factorisation Techniques......Page 187
Exercises III......Page 200
Computer Problems III......Page 206
RECOMMENDED FURTHER READING......Page 211
INDEX OF NOTATION......Page 212
INDEX......Page 213