INDICE: Preface v Notation xi Chapter 1 Fundamentals 1 1.0 Introduction 1 1.1 A Famous Sequence of Numbers 2 1.2 The Euclidean ALgorithm 6 The Oldest Algorithm Reversing the Euclidean Algorithm The Extended GCD Algorithm The Fundamental Theorem of Arithmetic Two Applications 1.3 Modular Arithmetic 25 1.4 Fast Powers 30 A Fast Alforithm for ExponentiationPowers of Matrices, Big-O Notation Chapter 2 Congruences, Equations, and Powers 41 2.0 Introduction 41 2.1 Solving Linear Congruences 41 Linear Diophantine Equations in Two Variables The Conductor An Importatnt Quadratic Congruence 2.2 The Chinese Remainder Theorem49 2.3 PowerMod Patterns 55 Fermat's Little Theorem More Patterns in Powers 2.4 Pseudoprimes 59 Using the Pseudoprime Test Chapter 3 Euler's Function 3.0 Introduction 65 3.1 Euler's Function 65 3.2 Perfect Numbers and Their Relatives72 The Sum of Divisors Function Perfect Numbers Amicalbe, Abundant, and Deficient Numbers 3.3 Euler's Theorem 81 3.4 Primitive Roots for Primes 84 The order of an Integer Primes Have PRimitive roots Repeating Decimals 3.5 Primitive Roots for COmposites 90 3.6 The Universal Exponent 93 Universal Exponents PowerTowers The Form of Carmichael Numbers Chapter 4 Prime Numbers 99 4.0 Introduction 99 4.1 The Number of Primes 100 We'll Never Run Out of Primes The Sieve of Eratosthenes Chebyshev's Theorem and Bertrand's Postulate 4.2 Prime Testing and Certification 114 Strong Pseudoprimes Industrial-Grade Primes Prime Certification Via Primitive Roots An Improvement Pratt Certificates 4.3 Refinements and Other Directions 131 Other PRimality Tests Strong Liars are Scarce Findingthe nth Prime 4.4 A Doszen Prime Mysteries 141 Chapter 5 Some Applications 145 5.0 Introduction 145 5.1 Coding Secrets 145 Tossing a Coin into a Well The RSA Cryptosystem Digital Signatures 5.2 The Yao Millionaire Problem 155 5.3 Check Digits 158 Basic Check Digit Schemes A Perfect Check Digit Method Beyond Perfection: Correcting Errors 5.4 Factoring Algorithms 167 Trial Division Fermat's Algorithm Pollard Rho Pollard p-1 The Current Scene Chapter 6 Quadratic Residues 179 6.0 Introduction 179 6.1 Pepin's Test 179 Quadratic Residues Pepin'sTest Primes Congruent to 1 (Mod 40 6.2 Proof of Quadratic Reciprocity 185 Gauss's Lemma Proof of Quadratic Recipocity Jacobi's Extension An Application to Factoring 6.3 Quadratic Equations 195 Chapter 7 Continuec Faction 201 7.0 Introduction 201 7.1 FInite COntinued Fractions 202 7.2 Infinite Continued Fractions 207 7.3 Periodic Continued Fractions 213 7.4 Pell's Equation 227 7.5 Archimedes and the Sun God's Cattle 232 Wurm's Version: Using Rectangular Bulls The Real Cattle Problem 7.6 Factoring via Continued Fractions 238 Chapter 8 Prime Testing with Lucas Sequences 247 8.0 Introduction 247 8.1 Divisibility Properties of Lucas Sequencese 248 8.2 Prime Tests Using Lucas Sequencesse 259 Lucas Certification The Lucas-Lehmer Algorithm Explained Luca Pseudoprimes Strong Quadratic Pseudoprimes Primality Testing's Holy Grail Chapter 9 Prime Imaginaries and Imaginary Primes 279 9.0 Introduction 279 9.1 Sums of Two Squares 279 9.2 The Gaussian Intergers 302 Complex Number Theory Gaussian Primes The Moat Problem The Gaussian Zoo 9.3 Higher Reciprocity 325 Appendix A. Maathematica Basics 333 1.0 Introduction 333 A.1 Plotting 335 A.2 Typesetting 338 Sending Files By E-Mail A.3 Types of Functions 341 A.4 Lists 343 A.5 Programs 345 A.6 Solving Equations 347 A.7 Symbolic Algebra 349 Appendix B Lucas Certificates Exist351 References 355 Index of Mathematica Objects 359 Subject Index 363
- ISBN: 978-0-470-41215-2
- Editorial: John Wiley & Sons
- Encuadernacion: Cartoné
- Páginas: 384
- Fecha Publicación: 10/10/2008
- Nº Volúmenes: 1
- Idioma: Inglés