Author | Bressoud, David M. author |
---|---|
Title | Factorization and Primality Testing [electronic resource] / by David M. Bressoud |
Imprint | New York, NY : Springer New York, 1989 |
Connect to | http://dx.doi.org/10.1007/978-1-4612-4544-5 |
Descript | XIV, 240 p. online resource |
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.3 Primitive 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