Factorization and Primality Testing
"About binomial theorems I'm teeming with a lot of news, With many cheerful facts about the square on the hypotenuse. " - William S. Gilbert (The Pirates of Penzance, Act I) The question of divisibility is arguably the oldest problem in mathematics. Ancient peoples observed the cycles...
| Main Author: | |
|---|---|
| Format: | eBook |
| Language: | English |
| Published: |
New York, NY
Springer New York
1989, 1989
|
| Edition: | 1st ed. 1989 |
| Series: | Undergraduate Texts in Mathematics
|
| Subjects: | |
| Online Access: | |
| Collection: | Springer Book Archives -2004 - Collection details see MPG.ReNa |
Table of Contents:
- 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
- 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