Prime Numbers and Computer Methods for Factorization
In this book the author treats four fundamental and apparently simple problems. They are: the number of primes below a given limit, the ap proximate number of primes, the recognition of prime numbers and the factorization of large numbers. A chapter on the details of the distribution of the primes...
| Main Author: | |
|---|---|
| Format: | eBook |
| Language: | English |
| Published: |
Boston, MA
Birkhäuser
1985, 1985
|
| Edition: | 1st ed. 1985 |
| Series: | Progress in Mathematics
|
| Subjects: | |
| Online Access: | |
| Collection: | Springer Book Archives -2004 - Collection details see MPG.ReNa |
Table of Contents:
- 1. The Number of Primes Below a Given Limit
- 2. The Primes Viewed at Large
- 3. Subtleties in the Distribution of Primes
- 4. The Recognition of Primes
- 5. Factorization
- 6. Prime Numbers and Cryptography
- Appendix 1. Basic Concepts in Higher Algebra
- Modules
- Euclid’s Algorithm
- The Labour Involved in Euclid’s Algorithm
- A Definition Taken from the Theory of Algorithms
- A Computer Program for Euclid’s Algorithm
- Reducing the Labour
- Binary Form of Euclid’s Algorithm
- Groups
- Lagrange’s Theorem. Cosets
- Abstract Groups. Isomorphic Groups
- The Direct Product of Two Given Groups
- Cyclic Groups
- Rings
- Zero Divisors
- Fields
- Mappings. Isomorphisms and Homomorphisms
- Group Characters
- The Conjugate or Inverse Character
- Homomorphisms and Group Characters
- Appendix 2. Basic Concepts in Higher Arithmetic
- Divisors. Common Divisors
- The Fundamental Theorem of Arithmetic
- Congruences
- Linear Congruences
- The Algebraic Structure of Aurifeuillian Numbers
- Appendix 7. Multiple-Precision Arithmetic
- Various Objectives for a Multiple-Precision Package
- How to Store Multi-Precise Integers
- Addition and Subtraction of Multi-Precise Integers
- Reduction in Length of Multi-Precise Integers
- Multiplication of Multi-Precise Integers
- Division of Multi-Precise Integers
- Input and Output of Multi-Precise Integers
- A Complete Package for Multiple-Precision Arithmetic
- Appendix 8. Fast Multiplication of Large Integers
- The Ordinary Multiplication Algorithm.
- Double Length Multiplication.
- Recursive Use of Double Length Multiplication Formula
- A Recursive Procedure for Squaring Large Integers
- Fractal Structure of Recursive Squaring
- Large Mersenne Primes
- Appendix 9. The Stieltjes Integral
- Functions With Jump Discontinuities
- The Riemann Integral
- Definition of the Stieltjes Integral
- Rules of Integration for Stieltjes Integrals
- Linear Congruences and Euclid’s Algorithm
- Systems of Linear Congruences
- Carmichael’s Function
- Carmichael’s Theorem
- Appendix 3. Quadratic Residues
- Legendre’s Symbol.
- Arithmetic Rules for Residues and Non-Residues
- The Law of Quadratic Reciprocity
- Jacobi’s Symbol
- Appendix 4. The Arithmetic of Quadratic Fields
- Appendix 5. Continued Fractions
- What Is a Continued Fraction?
- Regular Continued Fractions. Expansions
- Evaluating a Continued Fraction
- Continued Fractions as Approximations
- Euclid’s Algorithm and Continued Fractions
- Linear Diophantine Equations and Continued Fractions
- A Computer Program
- Continued Fraction Expansions of Square Roots
- Proof of Periodicity
- The Maximal Period-Lenath
- Short Periods
- Continued Fractions and Quadratic Residues
- Appendix 6. Algebraic Factors
- Factorization ofPolynomials
- The Cyclotomic Polynomials
- Aurifeuillian Factorizations
- Factorization Formulas
- Integration by Parts of Stieltjes Integrals
- The Mean Value Theorem
- Applications
- Tables
- Tatle 1. The Primes Belnw 12553
- Table 4. Factors of Fermat Numbers
- Table 7. Factors of Mersenne Numbers
- Table 32. Quadratic Residues
- Table 33. Gauss’ formulas for Cyclotomic Polynomials
- Table 34. Lucas’ formulas for Cyclotomic Polynomials