Монография (англ. яз.)
N.-Y.: Springer, 2012. - XVIII, 464 p. 20 ill. (Mode Birkhäuser Classics)
ISBN 978-08176-8297-2
e-ISBN 978-0-8176-8298-9
Является переизданием одноименной книги, изданной в 1994 г. издательством Birkhäuser (Boston, Birkhäuser, 1994, серия "Progress in Mathematics Vol, 126). Из предисловия бумажного издания книги:
В наше время почти поголовного использования компьютера практически у каждого человека в технологически развитом обществе обычно есть доступ к самой распространенной криптографической технологии из существующих - так называемой криптографической системе с открытым ключом RSA. Базисный элемент этой системы - разложение больших чисел на простые множители. Таким образом, древнее понятие теории чисел теперь играет важную роль в коммуникации миллионов людей, которые обладают куцыми или даже вовсе не владеют знаниями в элементарной математике. Эта книга призвана восполнить этот вопиющий пробел. Весьма успешное первое издание этой книги Ханса Ризеля теперь расширено и обновлено с целью удовлетворения потребностей исследователей, студентов, практиков криптографии и просто читателей - любителей математики. Оно включает важные достижения последних лет в вычислительной теории простых чисел и в факторизации, с добавлением заново вычисленных и расширенных таблиц, сопровождаемыми новыми таблицами, отражающими текущие исследования автора, его коллег и других исследователей.
В книге исследуются четыре фундаментальные задачи: вычисление количества простых чисел не превосходящих данной границы, различные оценки количества простых чисел, распознание простых чисел и факторизация больших чисел. Автор описывает конкретные алгоритмы и компьютерные программы, и по-возможности обсуждает как многие важные классические результаты, так и новые открытия. Включенные в книгу программы, написаны на языке Паскаль, что позволяет читателям при желании достаточно легко конвертировать эти программы на другие языки программирования. Независимая структура всех глав книги делает ее весьма удобной для чтения для самых разных групп читателей: математиков, студентов-числовиков и прочих исследователей в теории чисел и криптографии. Содержание: Preface
Contents
Notation The Number of Primes Below a Given Limit
What Is a Prime Number?
The Fundamental Theorem of Arithmetic
Which Numbers Are Primes? The Sieve of Eratosthenes
General Remarks Conceing Computer Programs
A Sieve Program
Compact Prime Tables
Hexadecimal Compact Prime Tables
Difference Between Consecutive Primes
The Number of Primes Below x
Meissel’s Formula
Evaluation of Pk(x, a)
Lehmer’s Formula
Computations
A Computation Using Meissel’s Formula
A Computation Using Lehmer’s Formula
A Computer Program Using Lehmer’s Formula
Mapes’ Method
Deduction of Formulas
A Worked Example
Mapes’ Algorithm
Programming Mapes’ Algorithm
Recent Developments
Results
Computational Complexity
Comparison Between the Methods Discussed
Bibliography The Primes Viewed at Large
Introduction
No Polynomial Can Produce Only Primes
Formulas Yielding All Primes
The Distribution of Primes Viewed at Large. Euclid’s Theorem
The Formulas of Gauss and Legendre for π(x). The Prime Number Theorem
The Chebyshev Function θ(x)
The Riemann Zeta-function
The Zeros of the Zeta-function
Conversion From f(x) Back to π(x)
The Riemann Prime Number Formula
The Sign of li(x) − π(x)
The Influence of the Complex Zeros of ζ(s) on π(x)
The Remainder Term in the Prime Number Theorem
Effective Inequalities for π(x), pn, and θ(x)
The Number of Primes in Arithmetic Progressions
Bibliography Subtleties in the Distribution of Primes
The Distribution of Primes in Short Intervals
Twins and Some Other Constellations of Primes
Admissible Constellations of Primes
The Hardy-Littlewood Constants
The Prime k-Tuples Conjecture
Theoretical Evidence in Favour of the Prime k-Tuples Conjecture
Numerical Evidence in Favour of the Prime k-Tuples Conjecture
The Second Hardy-Littlewood Conjecture
The Midpoint Sieve
Modification of the Midpoint Sieve
Construction of Superdense Admissible Constellations
Some Dense Clusters of Primes
The Distribution of Primes Between the Two Series 4n+1 and 4n+3
Graph of the Function π4,3(x)−π4,1(x)
The Negative Regions
The Negative Blocks
Large Gaps Between Consecutive Primes
The Cramér Conjecture
Bibliography The Recognition of Primes
Introduction
Tests of Primality and of Compositeness
Factorization Methods as Tests of Compositeness
Fermat's Theorem as Compositeness Test
Fermat's Theorem as Primality Test
Pseudoprimes and Probable Primes
A Computer Program for Fermat’s Test
The Labor Involved in a Fermat Test
Carmichael Numbers
Euler Pseudoprimes
Strong Pseudoprimes and a Primality Test
A Computer Program for Strong Pseudoprime Tests
Counts of Pseudoprimes and Carmichael Numbers
Rigorous Primality Proofs
Lehmer’s Converse of Fermat’s Theorem
Formal Proof of Theorem 4.3
Ad Hoc Search for a Primitive Root
The Use of Several Bases
Fermat Numbers and Pepin’s Theorem
Cofactors of Fermat Numbers
Generalized Fermat Numbers
A Relaxed Converse of Fermat’s Theorem
Proth’s Theorem
Tests of Compositeness for Numbers of the form Ν = h·2n±k
An Alteative Approach
Certificates of Primality
Primality Tests of Lucasian Type
Lucas Sequences
The Fibonacci Numbers
Large Subscripts
An Alteative Deduction
Divisibility Properties of the Numbers Un
Primality Proofs by Aid of Lucas Sequences
Lucas Tests for Mersenne Numbers
A Relaxation of Theorem 4.8
Pocklington’s Theorem
Lehmer-Pocklington’s Theorem
Pocklington-Type Theorems for Lucas Sequences
Primality Tests for Integers of the form Ν = h·2n−1, when 3∤h
Primality Tests for N=h·2n−1, when 3|h
The Combined Ν−1 and Ν+1 Test
Lucas Pseudoprimes
Mode Pnmality Proofs
The Jacobi Sum Pnmality Test
Three Lemmas
Lenstra’s Theorem
The Sets Ρ and Q
Running Time for the APRCL Test
Elliptic Curve Pnmality Proving, ECPP
The Goldwasser-Kilian Test
Atkin’s Test
Bibliography Classical Methods of Factorization
Introduction
When Do We Attempt Factorization?
Trial Division
A Computer Implementation of Trial Division
Euclid’s Algorithm as an Aid to Factorization
Fermat’s Factoring Method
Legendre’s Congruence
Euler’s Factoring Method
Gauss’ Factoring Method
Legendre’s Factoring Method
The Number of Prime Factors of Large Numbers
How Does a Typical Factorization Look?
The Erdős-Kac Theorem
The Distribution of Prime Factors of Various Sizes
Dickman’s Version of Theorem 5.4
A More Detailed Theory
The Size of the kth Largest Prime Factor of Ν
Smooth Integers
Searching for Factors of Certain Forms
Legendre’s Theorem for the Factors of Ν = an ± bn
Adaptation to Search for Factors of the Form p = 2kn+1
Adaptation of Trial Division
Adaptation of Fermat’s Factoring Method
Adaptation of Euclid’s Algorithm as an Aid to Factorization
Bibliography Mode Factorization Methods
Introduction
Choice of Method
Pollard’s (p−1)-Method
Phase 2 of the (p−1)-Method
The (p+1)-Method
Pollard’s rho Method
A Computer Program for Pollard’s rho Method
An Algebraic Description of Pollard’s rho Method
Brent’s Modification of Pollard’s rho Method
The Pollard-Brent Method for p = 2kn + 1
Shanks’ Factoring Method SQUFOF
A Computer Program for SQUFOF
Comparison Between Pollard’s rho Method and SQUFOF
Morrison and Brillhart’s Continued Fraction Method CFRAC
The Factor Base
An Example of a Factorization with CFRAC
Further Details of CFRAC
The Early Abort Strategy
Results Achieved with CFRAC
Running Time Analysis of CFRAC
The Quadratic Sieve, QS
Smallest Solutions to Q(x) = 0 mod p
Special Factors
Results Achieved with QS
The Multiple Polynomial Quadratic Sieve, MPQS
Results Achieved with MPQS
Running Time Analysis of QS and MPQS
The Schnorr-Lenstra Method
Two Categories of Factorization Methods
Lenstra’s Elliptic Curve Method, ECM
Phase 2 of ECM
The Choice of A, B, and P1
Running Times of ECM
Recent Results Achieved with ECM
The Number Field Sieve, NFS
Factoring Both in Ζ and in Z(z)
A Numerical Example
The General Number Field Sieve, GNFS
Running Times of NFS and GNFS
Results Achieved with NFS. Factorization of F9
Strategies in Factoring
How Fast Can a Factorization Algorithm Be?
Bibliography Prime Numbers and Cryptography
Practical Secrecy
Keys in Cryptography
Arithmetical Formulation
RSA Cryptosystems
How to Find the Recovery Exponent
A Worked Example
Selecting Keys
Finding Suitable Primes
The Fixed Points of an RSA System
How Safe is an RSA Cryptosystem?
Superior Factorization
Bibliography Appendix 1 Basic Concepts in Higher Algebra
Introduction
Modules
Euclid’s Algorithm
The Labor Involved in Euclid’s Algorithm
A Definition Taken from the Theory of Algorithms
A Computer Program for Euclid’s Algorithm
Reducing the Labor
Binary Form of Euclid’s Algorithm
The Diophantine Equation ax+by = c
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
Bibliography Appendix 2 Basic Concepts in Higher Arithmetic
Divisors. Common Divisors
The Fundamental Theorem of Arithmetic
Congruences
Linear Congruences
Linear Congruences and Euclid’s Algorithm
Systems of Linear Congruences
The Residue Classes mod p Constitute a Field
The Primitive Residue Classes mod p
The Structure of the Group Mn
Homomorphisms of Mq when q is a Prime
Carmichael’s Function
Carmichael’s Theorem
Bibliography Appendix 3 Quadratic Residues
Legendre’s Symbol
Arithmetic Rules for Residues and Non-Residues
Euler’s Criterion for the Computation of (a/p)
The Law of Quadratic Reciprocity
Jacobi’s Symbol
A PASCAL Function for Computing (a/n)
The Quadratic Congruence x2 ≡ c mod p
The Case p = 4k + 1
Bibliography Appendix 4 The Arithmetic of Quadratic Fields
Integers of Q(√D)
Units of Q(√D)
Associated Numbers in Q(√D)
Divisibility in Q(√D)
Fermat’s Theorem in Q(√D)
Primes in Q(√D)
Factorization of Integers in Q(√D)
Bibliography Appendix 5 Higher Algebraic Number Fields
Introduction
Algebraic Numbers
Numbers in Q(z). The Ring Z(z) of Integers in Q(z)
The Norm in Q(z). Units of Q(z)
Divisibility and Primes in Z(z)
The Field Q(∛−2) and the Ring Z(∛−2)
Primes in Z(∛−2)
Bibliography Appendix 6 Algebraic Factors
Introduction
Factorization of Polynomials
The Cyclotomic Polynomials
The Polynomial xn + yn
The Polynomial xn + ayn
Aurifeuillian Factorizations
Factorization Formulas
The Algebraic Structure of Aurifeuillian Numbers
A formula by Gauss for xn − yn
Bibliography Appendix 7 Elliptic Curves
Cubics
Rational Points on Rational Cubics
Homogeneous Coordinates
Elliptic Curves
Rational Points on Elliptic Curves
Bibliography Appendix 8 Continued Fractions
Introduction
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-Length
Short Periods
Continued Fractions and Quadratic Residues
Bibliography Appendix 9 Multiple-Precision Arithmetic
Introduction
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
A Computer Program for Pollard’s rho Method Appendix 10 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
Bibliography Appendix 11
Introduction
Functions With Jump Discontinuities
The Riemann Integral
Definition of the Stieltjes Integral
Rules of Integration for Stieltjes Integrals
Integration by Parts of Stieltjes Integrals
The Mean Value Theorem
Applications
Tables. For Contents, see page 374
List of Textbooks
Index
N.-Y.: Springer, 2012. - XVIII, 464 p. 20 ill. (Mode Birkhäuser Classics)
ISBN 978-08176-8297-2
e-ISBN 978-0-8176-8298-9
Является переизданием одноименной книги, изданной в 1994 г. издательством Birkhäuser (Boston, Birkhäuser, 1994, серия "Progress in Mathematics Vol, 126). Из предисловия бумажного издания книги:
В наше время почти поголовного использования компьютера практически у каждого человека в технологически развитом обществе обычно есть доступ к самой распространенной криптографической технологии из существующих - так называемой криптографической системе с открытым ключом RSA. Базисный элемент этой системы - разложение больших чисел на простые множители. Таким образом, древнее понятие теории чисел теперь играет важную роль в коммуникации миллионов людей, которые обладают куцыми или даже вовсе не владеют знаниями в элементарной математике. Эта книга призвана восполнить этот вопиющий пробел. Весьма успешное первое издание этой книги Ханса Ризеля теперь расширено и обновлено с целью удовлетворения потребностей исследователей, студентов, практиков криптографии и просто читателей - любителей математики. Оно включает важные достижения последних лет в вычислительной теории простых чисел и в факторизации, с добавлением заново вычисленных и расширенных таблиц, сопровождаемыми новыми таблицами, отражающими текущие исследования автора, его коллег и других исследователей.
В книге исследуются четыре фундаментальные задачи: вычисление количества простых чисел не превосходящих данной границы, различные оценки количества простых чисел, распознание простых чисел и факторизация больших чисел. Автор описывает конкретные алгоритмы и компьютерные программы, и по-возможности обсуждает как многие важные классические результаты, так и новые открытия. Включенные в книгу программы, написаны на языке Паскаль, что позволяет читателям при желании достаточно легко конвертировать эти программы на другие языки программирования. Независимая структура всех глав книги делает ее весьма удобной для чтения для самых разных групп читателей: математиков, студентов-числовиков и прочих исследователей в теории чисел и криптографии. Содержание: Preface
Contents
Notation The Number of Primes Below a Given Limit
What Is a Prime Number?
The Fundamental Theorem of Arithmetic
Which Numbers Are Primes? The Sieve of Eratosthenes
General Remarks Conceing Computer Programs
A Sieve Program
Compact Prime Tables
Hexadecimal Compact Prime Tables
Difference Between Consecutive Primes
The Number of Primes Below x
Meissel’s Formula
Evaluation of Pk(x, a)
Lehmer’s Formula
Computations
A Computation Using Meissel’s Formula
A Computation Using Lehmer’s Formula
A Computer Program Using Lehmer’s Formula
Mapes’ Method
Deduction of Formulas
A Worked Example
Mapes’ Algorithm
Programming Mapes’ Algorithm
Recent Developments
Results
Computational Complexity
Comparison Between the Methods Discussed
Bibliography The Primes Viewed at Large
Introduction
No Polynomial Can Produce Only Primes
Formulas Yielding All Primes
The Distribution of Primes Viewed at Large. Euclid’s Theorem
The Formulas of Gauss and Legendre for π(x). The Prime Number Theorem
The Chebyshev Function θ(x)
The Riemann Zeta-function
The Zeros of the Zeta-function
Conversion From f(x) Back to π(x)
The Riemann Prime Number Formula
The Sign of li(x) − π(x)
The Influence of the Complex Zeros of ζ(s) on π(x)
The Remainder Term in the Prime Number Theorem
Effective Inequalities for π(x), pn, and θ(x)
The Number of Primes in Arithmetic Progressions
Bibliography Subtleties in the Distribution of Primes
The Distribution of Primes in Short Intervals
Twins and Some Other Constellations of Primes
Admissible Constellations of Primes
The Hardy-Littlewood Constants
The Prime k-Tuples Conjecture
Theoretical Evidence in Favour of the Prime k-Tuples Conjecture
Numerical Evidence in Favour of the Prime k-Tuples Conjecture
The Second Hardy-Littlewood Conjecture
The Midpoint Sieve
Modification of the Midpoint Sieve
Construction of Superdense Admissible Constellations
Some Dense Clusters of Primes
The Distribution of Primes Between the Two Series 4n+1 and 4n+3
Graph of the Function π4,3(x)−π4,1(x)
The Negative Regions
The Negative Blocks
Large Gaps Between Consecutive Primes
The Cramér Conjecture
Bibliography The Recognition of Primes
Introduction
Tests of Primality and of Compositeness
Factorization Methods as Tests of Compositeness
Fermat's Theorem as Compositeness Test
Fermat's Theorem as Primality Test
Pseudoprimes and Probable Primes
A Computer Program for Fermat’s Test
The Labor Involved in a Fermat Test
Carmichael Numbers
Euler Pseudoprimes
Strong Pseudoprimes and a Primality Test
A Computer Program for Strong Pseudoprime Tests
Counts of Pseudoprimes and Carmichael Numbers
Rigorous Primality Proofs
Lehmer’s Converse of Fermat’s Theorem
Formal Proof of Theorem 4.3
Ad Hoc Search for a Primitive Root
The Use of Several Bases
Fermat Numbers and Pepin’s Theorem
Cofactors of Fermat Numbers
Generalized Fermat Numbers
A Relaxed Converse of Fermat’s Theorem
Proth’s Theorem
Tests of Compositeness for Numbers of the form Ν = h·2n±k
An Alteative Approach
Certificates of Primality
Primality Tests of Lucasian Type
Lucas Sequences
The Fibonacci Numbers
Large Subscripts
An Alteative Deduction
Divisibility Properties of the Numbers Un
Primality Proofs by Aid of Lucas Sequences
Lucas Tests for Mersenne Numbers
A Relaxation of Theorem 4.8
Pocklington’s Theorem
Lehmer-Pocklington’s Theorem
Pocklington-Type Theorems for Lucas Sequences
Primality Tests for Integers of the form Ν = h·2n−1, when 3∤h
Primality Tests for N=h·2n−1, when 3|h
The Combined Ν−1 and Ν+1 Test
Lucas Pseudoprimes
Mode Pnmality Proofs
The Jacobi Sum Pnmality Test
Three Lemmas
Lenstra’s Theorem
The Sets Ρ and Q
Running Time for the APRCL Test
Elliptic Curve Pnmality Proving, ECPP
The Goldwasser-Kilian Test
Atkin’s Test
Bibliography Classical Methods of Factorization
Introduction
When Do We Attempt Factorization?
Trial Division
A Computer Implementation of Trial Division
Euclid’s Algorithm as an Aid to Factorization
Fermat’s Factoring Method
Legendre’s Congruence
Euler’s Factoring Method
Gauss’ Factoring Method
Legendre’s Factoring Method
The Number of Prime Factors of Large Numbers
How Does a Typical Factorization Look?
The Erdős-Kac Theorem
The Distribution of Prime Factors of Various Sizes
Dickman’s Version of Theorem 5.4
A More Detailed Theory
The Size of the kth Largest Prime Factor of Ν
Smooth Integers
Searching for Factors of Certain Forms
Legendre’s Theorem for the Factors of Ν = an ± bn
Adaptation to Search for Factors of the Form p = 2kn+1
Adaptation of Trial Division
Adaptation of Fermat’s Factoring Method
Adaptation of Euclid’s Algorithm as an Aid to Factorization
Bibliography Mode Factorization Methods
Introduction
Choice of Method
Pollard’s (p−1)-Method
Phase 2 of the (p−1)-Method
The (p+1)-Method
Pollard’s rho Method
A Computer Program for Pollard’s rho Method
An Algebraic Description of Pollard’s rho Method
Brent’s Modification of Pollard’s rho Method
The Pollard-Brent Method for p = 2kn + 1
Shanks’ Factoring Method SQUFOF
A Computer Program for SQUFOF
Comparison Between Pollard’s rho Method and SQUFOF
Morrison and Brillhart’s Continued Fraction Method CFRAC
The Factor Base
An Example of a Factorization with CFRAC
Further Details of CFRAC
The Early Abort Strategy
Results Achieved with CFRAC
Running Time Analysis of CFRAC
The Quadratic Sieve, QS
Smallest Solutions to Q(x) = 0 mod p
Special Factors
Results Achieved with QS
The Multiple Polynomial Quadratic Sieve, MPQS
Results Achieved with MPQS
Running Time Analysis of QS and MPQS
The Schnorr-Lenstra Method
Two Categories of Factorization Methods
Lenstra’s Elliptic Curve Method, ECM
Phase 2 of ECM
The Choice of A, B, and P1
Running Times of ECM
Recent Results Achieved with ECM
The Number Field Sieve, NFS
Factoring Both in Ζ and in Z(z)
A Numerical Example
The General Number Field Sieve, GNFS
Running Times of NFS and GNFS
Results Achieved with NFS. Factorization of F9
Strategies in Factoring
How Fast Can a Factorization Algorithm Be?
Bibliography Prime Numbers and Cryptography
Practical Secrecy
Keys in Cryptography
Arithmetical Formulation
RSA Cryptosystems
How to Find the Recovery Exponent
A Worked Example
Selecting Keys
Finding Suitable Primes
The Fixed Points of an RSA System
How Safe is an RSA Cryptosystem?
Superior Factorization
Bibliography Appendix 1 Basic Concepts in Higher Algebra
Introduction
Modules
Euclid’s Algorithm
The Labor Involved in Euclid’s Algorithm
A Definition Taken from the Theory of Algorithms
A Computer Program for Euclid’s Algorithm
Reducing the Labor
Binary Form of Euclid’s Algorithm
The Diophantine Equation ax+by = c
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
Bibliography Appendix 2 Basic Concepts in Higher Arithmetic
Divisors. Common Divisors
The Fundamental Theorem of Arithmetic
Congruences
Linear Congruences
Linear Congruences and Euclid’s Algorithm
Systems of Linear Congruences
The Residue Classes mod p Constitute a Field
The Primitive Residue Classes mod p
The Structure of the Group Mn
Homomorphisms of Mq when q is a Prime
Carmichael’s Function
Carmichael’s Theorem
Bibliography Appendix 3 Quadratic Residues
Legendre’s Symbol
Arithmetic Rules for Residues and Non-Residues
Euler’s Criterion for the Computation of (a/p)
The Law of Quadratic Reciprocity
Jacobi’s Symbol
A PASCAL Function for Computing (a/n)
The Quadratic Congruence x2 ≡ c mod p
The Case p = 4k + 1
Bibliography Appendix 4 The Arithmetic of Quadratic Fields
Integers of Q(√D)
Units of Q(√D)
Associated Numbers in Q(√D)
Divisibility in Q(√D)
Fermat’s Theorem in Q(√D)
Primes in Q(√D)
Factorization of Integers in Q(√D)
Bibliography Appendix 5 Higher Algebraic Number Fields
Introduction
Algebraic Numbers
Numbers in Q(z). The Ring Z(z) of Integers in Q(z)
The Norm in Q(z). Units of Q(z)
Divisibility and Primes in Z(z)
The Field Q(∛−2) and the Ring Z(∛−2)
Primes in Z(∛−2)
Bibliography Appendix 6 Algebraic Factors
Introduction
Factorization of Polynomials
The Cyclotomic Polynomials
The Polynomial xn + yn
The Polynomial xn + ayn
Aurifeuillian Factorizations
Factorization Formulas
The Algebraic Structure of Aurifeuillian Numbers
A formula by Gauss for xn − yn
Bibliography Appendix 7 Elliptic Curves
Cubics
Rational Points on Rational Cubics
Homogeneous Coordinates
Elliptic Curves
Rational Points on Elliptic Curves
Bibliography Appendix 8 Continued Fractions
Introduction
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-Length
Short Periods
Continued Fractions and Quadratic Residues
Bibliography Appendix 9 Multiple-Precision Arithmetic
Introduction
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
A Computer Program for Pollard’s rho Method Appendix 10 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
Bibliography Appendix 11
Introduction
Functions With Jump Discontinuities
The Riemann Integral
Definition of the Stieltjes Integral
Rules of Integration for Stieltjes Integrals
Integration by Parts of Stieltjes Integrals
The Mean Value Theorem
Applications
Tables. For Contents, see page 374
List of Textbooks
Index