1 Unique Factorization and the Euclidean Algorithm. - 1. 1 A theorem of Euclid and some of its consequences. - 1. 2 The Fundamental Theorem of Arithmetic. - 1. 3 The Euclidean Algorithm. - 1. 4 The Euclidean Algorithm in practice. - 1. 5 Continued fractions a first glance. - 1. 6 Exercises. - 2 Primes and Perfect Numbers. - 2. 1 The Number of Primes. - 2. 2 The Sieve of Eratosthenes. - 2. 3 Trial Division. - 2. 4 Perfect Numbers. - 2. 5 Mersenne Primes. - 2. 6 Exercises. - 3 Fermat Euler and Pseudoprimes. - 3. 1 Fermat's Observation. - 3. 2 Pseudoprimes. - 3. 3 Fast Exponentiation. - 3. 4 A Theorem of Euler. - 3. 5 Proof of Fermat's Observation. - 3. 6 Implications for Perfect Numbers. - 3. 7 Exercises. - 4 The RSA Public Key Crypto-System. - 4. 1 The Basic Idea. - 4. 2 An Example. - 4. 3 The Chinese Remainder Theorem. - 4. 4 What if the Moduli are not Relatively Prime?. - 4. 5 Properties of Euler's ø Function. - Exercises. - 5 Factorization Techniques from Fermat to Today. - 5. 1 Fermat's Algorithm. - 5. 2 Kraitchik's Improvement. - 5. 3 Pollard Rho. - 5. 4 Pollard p 1. - 5. 5 Some Musings. - 5. 6 Exercises. - 6 Strong Pseudoprimes and Quadratic Residues. - 6. 1 The Strong Pseudoprime Test. - 6. 2 Refining Fermat's Observation. - 6. 3 No Strong Carmichael Numbers. - 6. 4 Exercises. - 7 Quadratic Reciprocity. - 7. 1 The Legendre Symbol. - 7. 2 The Legendre symbol for small bases. - 7. 3 Quadratic Reciprocity. - 7. 4 The Jacobi Symbol. - 7. 5 Computing the Legendre Symbol. - 7. 6 Exercises. - 8 The Quadratic Sieve. - 8. 1 Dixon's Algorithm. - 8. 2 Pomerance's Improvement. - 8. 3 Solving Quadratic Congruences. - 8. 4 Sieving. - 8. 5 Gaussian Elimination. - 8. 6 Large Primes and Multiple Polynomials. - 8. 7 Exercises. - 9 Primitive Roots and a Test for Primality. - 9. 1 Orders and Primitive Roots. - 9. 2 Properties of Primitive Roots. - 9. 3Primitive Roots for Prime Moduli. - 9. 4 A Test for Primality. - 9. 5 More on Primality Testing. - 9. 6 The Rest of Gauss' Theorem. - 9. 7 Exercises. - 10 Continued Fractions. - 10. 1 Approximating the Square Root of 2. - 10. 2 The Bháscara-Brouncker Algorithm. - 10. 3 The Bháscara-Brouncker Algorithm Explained. - 10. 4 Solutions Really Exist. - 10. 5 Exercises. - 11 Continued Fractions Continued Applications. - 11. 1 CFRAC. - 11. 2 Some Observations on the Bháscara-Brouncker Algorithm. - 11. 3 Proofs of the Observations. - 11. 4 Primality Testing with Continued Fractions. - 11. 5 The Lucas-Lehmer Algorithm Explained. - 11. 6 Exercises. - 12 Lucas Sequences. - 12. 1 Basic Definitions. - 12. 2 Divisibility Properties. - 12. 3 Lucas' Primality Test. - 12. 4 Computing the V's. - 12. 5 Exercises. - 13 Groups and Elliptic Curves. - 13. 1 Groups. - 13. 2 A General Approach to Primality Tests. - 13. 3 A General Approach to Factorization. - 13. 4 Elliptic Curves. - 13. 5 Elliptic Curves Modulo p. - 13. 6 Exercises. - 14 Applications of Elliptic Curves. - 14. 1 Computation on Elliptic Curves. - 14. 2 Factorization with Elliptic Curves. - 14. 3 Primality Testing. - 14. 4 Quadratic Forms. - 14. 5 The Power Residue Symbol. - 14. 6 Exercises. - The Primes Below 5000. Language: English