Muutke küpsiste eelistusi

Prime Numbers and Computer Methods for Factorization 2nd ed. 2012 [Pehme köide]

  • Formaat: Paperback / softback, 464 pages, kõrgus x laius: 235x155 mm, kaal: 735 g, 20 Illustrations, black and white; XVIII, 464 p. 20 illus., 1 Paperback / softback
  • Sari: Modern Birkhauser Classics
  • Ilmumisaeg: 22-Nov-2011
  • Kirjastus: Birkhauser Boston Inc
  • ISBN-10: 081768297X
  • ISBN-13: 9780817682972
Teised raamatud teemal:
  • Pehme köide
  • Hind: 64,45 €*
  • * hind on lõplik, st. muud allahindlused enam ei rakendu
  • Tavahind: 75,82 €
  • Säästad 15%
  • Raamatu kohalejõudmiseks kirjastusest kulub orienteeruvalt 2-4 nädalat
  • Kogus:
  • Lisa ostukorvi
  • Tasuta tarne
  • Tellimisaeg 2-4 nädalat
  • Lisa soovinimekirja
  • Formaat: Paperback / softback, 464 pages, kõrgus x laius: 235x155 mm, kaal: 735 g, 20 Illustrations, black and white; XVIII, 464 p. 20 illus., 1 Paperback / softback
  • Sari: Modern Birkhauser Classics
  • Ilmumisaeg: 22-Nov-2011
  • Kirjastus: Birkhauser Boston Inc
  • ISBN-10: 081768297X
  • ISBN-13: 9780817682972
Teised raamatud teemal:
From the original hard cover edition:

In the modern age of almost universal computer usage, practically every individual in a technologically developed society has routine access to the most up-to-date cryptographic technology that exists, the so-called RSA public-key cryptosystem. A major component of this system is the factorization of large numbers into their primes. Thus an ancient number-theory concept now plays a crucial role in communication among millions of people who may have little or no knowledge of even elementary mathematics. 

Hans Riesels highly successful first edition of this book has now been enlarged and updated with the goal of satisfying the needs of researchers, students, practitioners of cryptography, and non-scientific readers with a mathematical inclination. It includes important advances in computational prime number theory and in factorization as well as re-computed and enlarged tables, accompanied by new tables reflecting current research by both the author and his coworkers and by independent researchers.  

The book treats four fundamental problems: the number of primes below a given limit, the approximate number of primes, the recognition of primes and the factorization of large numbers. The author provides explicit algorithms and computer programs, and has attempted to discuss as many of the classically important results as possible, as well as the most recent discoveries. The programs include are written in PASCAL to allow readers to translate the programs into the language of their own computers.  

The independent structure of each chapter of the book makes it highly readable for a wide variety of mathematicians, students of applied number theory, and others interested in both study and research in number theory and cryptography.

Arvustused

Here is an outstanding technical monograph on recursive number theory and its numerous automated techniques. It successfully passes a critical milestone not allowed to many books, viz., a second edition... All in all, this handy volume continues to be an attractive combination of number-theoretic precision, practicality, and theory with a rich blend of computer science.  Zentralblatt MATH

The book...is an enthusiastic introduction to some of the ideas concerned with primes and factorization. It should be of interest to anyone who would like to learn about the use of computers in number theory. Mathematical Reviews

Chapter 1 The Number of Primes Below a Given Limit
What Is a Prime Number?
1(1)
The Fundamental Theorem of Arithmetic
2(1)
Which Numbers Are Primes? The Sieve of Eratosthenes
2(2)
General Remarks Concerning Computer Programs
4(1)
A Sieve Program
5(2)
Compact Prime Tables
7(2)
Hexadecimal Compact Prime Tables
9(1)
Difference Between Consecutive Primes
9(1)
The Number of Primes Below x
10(2)
Meissel's Formula
12(1)
Evaluation of Pk(x, a)
12(1)
Lehmer's Formula
13(1)
Computations
14(4)
A Computation Using Meissel's Formula
18(2)
A Computation Using Lehmer's Formula
20(2)
A Computer Program Using Lehmer's Formula
22(1)
Mapes' Method
23(1)
Deduction of Formulas
24(2)
A Worked Example
26(4)
Mapes' Algorithm
30(2)
Programming Mapes' Algorithm
32(1)
Recent Developments
33(1)
Results
34(1)
Computational Complexity
35(1)
Comparison Between the Methods Discussed
35(1)
Bibliography
36(1)
Chapter 2 The Primes Viewed at Large
Introduction
37(1)
No Polynomial Can Produce Only Primes
37(2)
Formulas Yielding All Primes
39(1)
The Distribution of Primes Viewed at Large. Euclid's Theorem
40(1)
The Formulas of Gauss and Legendre for π(x). The Prime Number Theorem
41(3)
The Chebyshev Function θ(x)
44(1)
The Riemann Zeta-function
44(3)
The Zeros of the Zeta-function
47(2)
Conversion From f(x) Back to π(x)
49(1)
The Riemann Prime Number Formula
50(2)
The Sign of li x - π(x)
52(1)
The Influence of the Complex Zeros of ξ(i) on π(x)
53(3)
The Remainder Term in the Prime Number Theorem
56(1)
Effective Inequalities for π(x), pn, and θ(x)
56(1)
The Number of Primes in Arithmetic Progressions
57(1)
Bibliography
58(2)
Chapter 3 Subtleties in the Distribution of Primes
The Distribution of Primes in Short Intervals
60(1)
Twins and Some Other Constellations of Primes
60(2)
Admissible Constellations of Primes
62(2)
The Hardy-Littlewood Constants
64(2)
The Prime k-Tuples Conjecture
66(1)
Theoretical Evidence in Favour of the Prime k-Tuples Conjecture
67(1)
Numerical Evidence in Favour of the Prime k-Tuples Conjecture
68(1)
The Second Hardy-Littlewood Conjecture
68(2)
The Midpoint Sieve
70(1)
Modification of the Midpoint Sieve
70(1)
Construction of Superdense Admissible Constellations
71(2)
Some Dense Clusters of Primes
73(1)
The Distribution of Primes Between the Two Series 4n + 1 and 4n + 3
73(1)
Graph of the Function π4,3(x)- π4,1(x)
74(1)
The Negative Regions
74(3)
The Negative Blocks
77(1)
Large Gaps Between Consecutive Primes
78(1)
The Cramer Conjecture
79(3)
Bibliography
82(2)
Chapter 4 The Recognition of Primes
Introduction
84(1)
Tests of Primality and of Compositeness
84(1)
Factorization Methods as Tests of Compositeness
85(1)
Fermat's Theorem as Compositeness Test
85(1)
Fermat's Theorem as Primality Test
85(1)
Pseudoprimes and Probable Primes
86(1)
A Computer Program for Fermat's Test
87(1)
The Labor Involved in a Fermat Test
88(1)
Carmichael Numbers
89(1)
Euler Pseudoprimes
90(1)
Strong Pseudoprimes and a Primality Test
91(2)
A Computer Program for Strong Pseudoprime Tests
93(1)
Counts of Pseudoprimes and Carmichael Numbers
94(1)
Rigorous Primality Proofs
95(1)
Lehmer's Converse of Fermat's Theorem
96(1)
Formal Proof of Theorem 4.3
97(1)
Ad Hoc Search for a Primitive Root
98(1)
The Use of Several Bases
99(1)
Fermat Numbers and Pepin's Theorem
100(2)
Cofactors of Fermat Numbers
102(1)
Generalized Fermat Numbers
102(1)
A Relaxed Converse of Fermat's Theorem
103(1)
Proth's Theorem
104(1)
Tests of Compositeness for Numbers of the form N = h2n ± k
105(1)
An Alternative Approach
105(1)
Certificates of Primality
106(1)
Primality Tests of Lucasian Type
107(1)
Lucas Sequences
107(1)
The Fibonacci Numbers
108(1)
Large Subscripts
108(3)
An Alternative Deduction
111(1)
Divisibility Properties of the Numbers Un
112(3)
Primality Proofs by Aid of Lucas Sequences
115(2)
Lucas Tests for Mersenne Numbers
117(3)
A Relaxation of Theorem 4.8
120(1)
Pocklington's Theorem
121(1)
Lehmer-Pocklington's Theorem
122(1)
Pocklington-Type Theorems for Lucas Sequences
123(1)
Primality Tests for Integers of the form N = h 2n - 1, when 3|h
124(1)
Primality Tests for N = h 2n - 1, when 3|h
125(4)
The Combined N - 1 and N + 1 Test
129(1)
Lucas Pseudoprimes
130(1)
Modern Primality Proofs
130(1)
The Jacobi Sum Primality Test
131(1)
Three Lemmas
132(2)
Lenstra's Theorem
134(1)
The Sets P and Q
135(1)
Running Time for the APRCL Test
136(1)
Elliptic Curve Primality Proving, ECPP
136(1)
The Goldwasser-Kilian Test
137(1)
Atkin's Test
138(1)
Bibliography
139(2)
Chapter 5 Classical Methods of Factorization
Introduction
141(1)
When Do We Attempt Factorization?
141(1)
Trial Division
141(2)
A Computer Implementation of Trial Division
143(2)
Euclid's Algorithm as an Aid to Factorization
145(2)
Fermat's Factoring Method
147(2)
Legendre's Congruence
149(2)
Euler's Factoring Method
151(1)
Gauss' Factoring Method
152(3)
Legendre's Factoring Method
155(1)
The Number of Prime Factors of Large Numbers
156(1)
How Does a Typical Factorization Look?
157(1)
The Erdos-Kac Theorem
158(1)
The Distribution of Prime Factors of Various Sizes
159(2)
Dickman's Version of Theorem 5.4
161(1)
A More Detailed Theory
161(1)
The Size of the kth Largest Prime Factor of N
162(2)
Smooth Integers
164(1)
Searching for Factors of Certain Forms
165(1)
Legendre's Theorem for the Factors of N = an ± bn
165(4)
Adaptation to Search for Factors of the Form p = 2kn + 1
169(1)
Adaptation of Trial Division
169(1)
Adaptation of Fermat's Factoring Method
170(1)
Adaptation of Euclid's Algorithm as an Aid to Factorization
171(1)
Bibliography
171(2)
Chapter 6 Modern Factorization Methods
Introduction
173(1)
Choice of Method
173(1)
Pollard's (p - 1)-Method
174(2)
Phase 2 of the (p - 1)-Method
176(1)
The (p + 1)-Method
177(1)
Pollard's rho Method
177(3)
A Computer Program for Pollard's rho Method
180(2)
An Algebraic Description of Pollard's rho Method
182(1)
Brent's Modification of Pollard's rho Method
183(2)
The Pollard-Brent Method for p = 2kn + 1
185(1)
Shanks' Factoring Method SQUFOF
186(4)
A Computer Program for SQUFOF
190(3)
Comparison Between Pollard's rho Method and SQUFOF
193(1)
Morrison and Brillhart's Continued Fraction Method CFRAC
193(1)
The Factor Base
194(2)
An Example of a Factorization with CFRAC
196(4)
Further Details of CFRAC
200(2)
The Early Abort Strategy
202(1)
Results Achieved with CFRAC
203(1)
Running Time Analysis of CFRAC
204(1)
The Quadratic Sieve, QS
204(1)
Smallest Solutions to Q(x) ≡ 0 mod p
205(1)
Special Factors
206(1)
Results Achieved with QS
206(1)
The Multiple Polynomial Quadratic Sieve, MPQS
207(1)
Results Achieved with MPQS
207(1)
Running Time Analysis of QS and MPQS
208(1)
The Schnorr-Lenstra Method
209(1)
Two Categories of Factorization Methods
209(1)
Lenstra's Elliptic Curve Method, ECM
210(1)
Phase 2 of ECM
210(2)
The Choice of A, B, and P1
212(1)
Running Times of ECM
212(2)
Recent Results Achieved with ECM
214(1)
The Number Field Sieve, NFS
214(1)
Factoring Both in Z and in Z(z)
215(1)
A Numerical Example
215(1)
The General Number Field Sieve, GNFS
216(1)
Running Times of NFS and GNFS
217(1)
Results Achieved with NFS. Factorization of F9
218(1)
Strategies in Factoring
219(2)
How Fast Can a Factorization Algorithm Be?
221(3)
Bibliography
224(2)
Chapter 7 Prime Numbers and Cryptography
Practical Secrecy
226(1)
Keys in Cryptography
226(2)
Arithmetical Formulation
228(1)
RSA Cryptosystems
228(1)
How to Find the Recovery Exponent
229(1)
A Worked Example
230(3)
Selecting Keys
233(1)
Finding Suitable Primes
234(1)
The Fixed Points of an RSA System
235(1)
How Safe is an RSA Cryptosystem?
236(1)
Superior Factorization
237(1)
Bibliography
237(2)
Appendix 1 Basic Concepts in Higher Algebra
Introduction
239(1)
Modules
239(1)
Euclid's Algorithm
240(2)
The Labor Involved in Euclid's Algorithm -
242(1)
A Definition Taken from the Theory of Algorithms
242(1)
A Computer Program for Euclid's Algorithm
243(1)
Reducing the Labor
244(1)
Binary Form of Euclid's Algorithm
244(2)
The Diophantine Equation ax + by = c
246(1)
Groups
246(2)
Lagrange's Theorem. Cosets
248(2)
Abstract Groups. Isomorphic Groups
250(21)
The Direct Product of Two Given Groups
251(1)
Cyclic Groups
252(1)
Rings
252(1)
Zero Divisors
253(2)
Fields
255(2)
Mappings. Isomorphisms and Homomorphisms
257(1)
Group Characters
258(1)
The Conjugate or Inverse Character
259(1)
Homomorphisms and Group Characters
260(1)
Bibliography
260(1)
Appendix 2 Bask Concepts in Higher Arithmetic
Divisors. Common Divisors
261(1)
The Fundamental Theorem of Arithmetic
261(1)
Congruences
262(2)
Linear Congruences
264(1)
Linear Congruences and Euclid's Algorithm
265(1)
Systems of Linear Congruences
266(1)
The Residue Classesmod p Constitute a Field
267(1)
The Primitive Residue Classesmod p
268(2)
The Structure of the Group Mn
270(2)
Homomorphisms of Mq when q is a Prime
272(1)
Carmichael's Function
273(1)
Carmichael's Theorem
274(1)
Bibliography
275(1)
Appendix 3 Quadratic Residues
Legendre's Symbol
276(1)
Arithmetic Rules for Residues and Non-Residues
276(2)
Euler's Criterion for the Computation of (a / p)
278(1)
The Law of Quadratic Reciprocity
279(2)
Jacobi's Symbol
281(2)
A PASCAL Function for Computing (a / n)
283(1)
The Quadratic Congruence x2 ≡ c mod p
284(1)
The Case p = 4k + 1
284(1)
Bibliography
285(1)
Appendix 4 The Arithmetic of Quadratic Fields
Integers of Q(√D)
286(3)
Units of Q(√D)
289(1)
Associated Numbers in Q(√D)
290(1)
Divisibility in Q(√D)
290(1)
Fermat's Theorem in Q(√D)
291(2)
Primes in Q(√D)
293(2)
Factorization of Integers in Q(√D)
295(1)
Bibliography
296(1)
Appendix 5 Higher Algebraic Number Fields
Introduction
297(1)
Algebraic Numbers
297(1)
Numbers in Q(z). The Ring Z(z) of Integers in Q(z)
298(1)
The Norm in Q(z). Units of Q(z)
298(1)
Divisibility and Primes in Z(z)
299(1)
The Field Q(3√-2) and the Ring Z(3√-2)
299(1)
Primes in Z(3√-2)
300(3)
Bibliography
303(1)
Appendix 6 Algebraic Factors
Introduction
304(1)
Factorization of Polynomials
304(1)
The Cyclotomic Polynomials
305(3)
The Polynomial xn + yn
308(1)
The Polynomial xn + ayn
308(1)
Aurifeuillian Factorizations
309(1)
Factorization Formulas
310(4)
The Algebraic Structure of Aurifeuillian Numbers
314(1)
A formula by Gauss for xn - yn
315(1)
Bibliography
316(1)
Appendix 7 Elliptic Curves
Cubics
317(2)
Rational Points on Rational Cubics
319(1)
Homogeneous Coordinates
319(1)
Elliptic Curves
320(1)
Rational Points on Elliptic Curves
321(5)
Bibliography
326(1)
Appendix 8 Continued Fractions
Introduction
327(1)
What Is a Continued Fraction?
327(1)
Regular Continued Fractions. Expansions
328(1)
Evaluating a Continued Fraction
329(3)
Continued Fractions as Approximations
332(2)
Euclid's Algorithm and Continued Fractions
334(1)
Linear Diophantine Equations and Continued Fractions
334(1)
A Computer Program
335(2)
Continued Fraction Expansions of Square Roots
337(1)
Proof of Periodicity
338(2)
The Maximal Period-Length
340(1)
Short Periods
341(1)
Continued Fractions and Quadratic Residues
341(1)
Bibliography
342(1)
Appendix 9 Multiple-Precision Arithmetic
Introduction
343(1)
Various Objectives for a Multiple-Precision Package
343(1)
How to Store Multi-Precise Integers
344(1)
Addition and Subtraction of Multi-Precise Integers
345(1)
Reduction in Length of Multi-Precise Integers
346(1)
Multiplication of Multi-Precise Integers
346(2)
Division of Multi-Precise Integers
348(1)
Input and Output of Multi-Precise Integers
349(1)
A Complete Package for Multiple-Precision Arithmetic
349(6)
A Computer Program for Pollard's rho Method
355(2)
Appendix 10 Fast Multiplication of Large Integers
The Ordinary Multiplication Algorithm
357(1)
Double Length Multiplication
358(2)
Recursive Use of Double Length Multiplication Formula
360(1)
A Recursive Procedure for Squaring Large Integers
361(3)
Fractal Structure of Recursive Squaring
364(1)
Large Mersenne Primes
364(1)
Bibliography
364(1)
Appendix 11 The Stieltjes Integral
Introduction
365(1)
Functions With Jump Discontinuities
365(1)
The Riemann Integral
366(1)
Definition of the Stieltjes Integral
367(2)
Rules of Integration for Stieltjes Integrals
369(1)
Integration by Parts of Stieltjes Integrals
370(1)
The Mean Value Theorem
371(1)
Applications
372(2)
Tables. For Contents 374(83)
List of Textbooks 457(1)
Index 458