Prime numbers : a computational perspective

>> Google Books

所蔵情報QRコード

Prime numbers : a computational perspective / Richard Crandall, Carl Pomerance

資料種別:

図書

出版情報:

New York : Springer, c2001

形態:

xv, 547 p. ; 25 cm

著者名:

ISBN:

9780387947778 [0387947779]

書誌ID:

BA51739188

子書誌情報

フルテキスト

所蔵情報

他の版・巻

書誌詳細

注記:

Includes bibliographical references and index

主題:

Numbers, Prime

言語:

英語

目次情報:

Preface

Primes! / 1：

Problems and progress / 1.1：

Fundamental theorem and fundamental problem / 1.1.1：

Technological and algorithmic progress / 1.1.2：

The infinitude of primes / 1.1.3：

Asymptotic relations and order nomenclature / 1.1.4：

How primes are distributed / 1.1.5：

Celebrated conjectures and curiosities / 1.2：

Twin primes / 1.2.1：

Prime k-tuples and hypothesis H / 1.2.2：

The Goldbach conjecture / 1.2.3：

The convexity question / 1.2.4：

Prime-producing formulae / 1.2.5：

Primes of special form / 1.3：

Mersenne primes / 1.3.1：

Fermat numbers / 1.3.2：

Certain presumably rare primes / 1.3.3：

Analytic number theory / 1.4：

The Riemann zeta function / 1.4.1：

Computational successes / 1.4.2：

Dirichlet L-functions / 1.4.3：

Exponential sums / 1.4.4：

Smooth numbers / 1.4.5：

Exercises / 1.5：

Research problems / 1.6：

Number-Theoretical Tools / 2：

Modular arithmetic / 2.1：

Greatest common divisor and inverse / 2.1.1：

Powers / 2.1.2：

Chinese remainder theorem / 2.1.3：

Polynomial arithmetic / 2.2：

Greatest common divisor for polynomials / 2.2.1：

Finite fields / 2.2.2：

Squares and roots / 2.3：

Quadratic residues / 2.3.1：

Square roots / 2.3.2：

Finding polynomial roots / 2.3.3：

Representation by quadratic forms / 2.3.4：

Recognizing Primes and Composites / 2.4：

Trial division / 3.1：

Divisibility tests / 3.1.1：

Practical considerations / 3.1.2：

Theoretical considerations / 3.1.4：

Sieving / 3.2：

Sieving to recognize primes / 3.2.1：

Eratosthenes pseudocode / 3.2.2：

Sieving to construct a factor table / 3.2.3：

Sieving to construct complete factorizations / 3.2.4：

Sieving to recognize smooth numbers / 3.2.5：

Sieving a polynomial / 3.2.6：

Recognizing smooth numbers / 3.2.7：

Pseudoprimes / 3.4：

Fermat pseudoprimes / 3.4.1：

Carmichael numbers / 3.4.2：

Probable primes and witnesses / 3.5：

The least witness for n / 3.5.1：

Lucas pseudoprimes / 3.6：

Fibonacci and Lucas pseudoprimes / 3.6.1：

Grantham's Frobenius test / 3.6.2：

Implementing the Lucas and quadratic Frobenius tests / 3.6.3：

Theoretical considerations and stronger tests / 3.6.4：

The general Frobenius test / 3.6.5：

Counting primes / 3.7：

Combinatorial method / 3.7.1：

Analytic method / 3.7.2：

Primality Proving / 3.8：

The n - 1 test / 4.1：

The Lucas theorem and Pepin test / 4.1.1：

Partial factorization / 4.1.2：

Succinct certificates / 4.1.3：

The n + 1 test / 4.2：

The Lucas-Lehmer test / 4.2.1：

An improved n + 1 test, and a combined n[superscript 2] - 1 test / 4.2.2：

Divisors in residue classes / 4.2.3：

The finite field primality test / 4.3：

Gauss and Jacobi sums / 4.4：

Gauss sums test / 4.4.1：

Jacobi sums test / 4.4.2：

The primality test of Agrawal, Kayal, and Saxena (AKS test) / 4.5：

Primality testing with roots of unity / 4.5.1：

The complexity of Algorithm 4.5.1 / 4.5.2：

Primality testing with Gaussian periods / 4.5.3：

A quartic time primality test / 4.5.4：

Exponential Factoring Algorithms / 4.6：

Squares / 5.1：

Fermat method / 5.1.1：

Lehman method / 5.1.2：

Factor sieves / 5.1.3：

Monte Carlo methods / 5.2：

Pollard rho method for factoring / 5.2.1：

Pollard rho method for discrete logarithms / 5.2.2：

Pollard lambda method for discrete logarithms / 5.2.3：

Baby-steps, giant-steps / 5.3：

Pollard p - 1 method / 5.4：

Polynomial evaluation method / 5.5：

Binary quadratic forms / 5.6：

Quadratic form fundamentals / 5.6.1：

Factoring with quadratic form representations / 5.6.2：

Composition and the class group / 5.6.3：

Ambiguous forms and factorization / 5.6.4：

Subexponential Factoring Algorithms / 5.7：

The quadratic sieve factorization method / 6.1：

Basic QS / 6.1.1：

Basic QS: A summary / 6.1.2：

Fast matrix methods / 6.1.3：

Large prime variations / 6.1.4：

Multiple polynomials / 6.1.5：

Self initialization / 6.1.6：

Zhang's special quadratic sieve / 6.1.7：

Number field sieve / 6.2：

Basic NFS: Strategy / 6.2.1：

Basic NFS: Exponent vectors / 6.2.2：

Basic NFS: Complexity / 6.2.3：

Basic NFS: Obstructions / 6.2.4：

Basic NFS: Square roots / 6.2.5：

Basic NFS: Summary algorithm / 6.2.6：

NFS: Further considerations / 6.2.7：

Rigorous factoring / 6.3：

Index-calculus method for discrete logarithms / 6.4：

Discrete logarithms in prime finite fields / 6.4.1：

Discrete logarithms via smooth polynomials and smooth algebraic integers / 6.4.2：

Elliptic Curve Arithmetic / 6.5：

Elliptic curve fundamentals / 7.1：

Elliptic arithmetic / 7.2：

The theorems of Hasse, Deuring, and Lenstra / 7.3：

Elliptic curve method / 7.4：

Basic ECM algorithm / 7.4.1：

Optimization of ECM / 7.4.2：

Counting points on elliptic curves / 7.5：

Shanks-Mestre method / 7.5.1：

Schoof method / 7.5.2：

Atkin-Morain method / 7.5.3：

Elliptic curve primality proving (ECPP) / 7.6：

Goldwasser-Kilian primality test / 7.6.1：

Atkin-Morain primality test / 7.6.2：

Fast primality-proving via ellpitic curves (fastECPP) / 7.6.3：

The Ubiquity of Prime Numbers / 7.7：

Cryptography / 8.1：

Diffie-Hellman key exchange / 8.1.1：

RSA cryptosystem / 8.1.2：

Elliptic curve cryptosystems (ECCs) / 8.1.3：

Coin-flip protocol / 8.1.4：

Random-number generation / 8.2：

Modular methods / 8.2.1：

Quasi-Monte Carlo (qMC) methods / 8.3：

Discrepancy theory / 8.3.1：

Specific qMC sequences / 8.3.2：

Primes on Wall Street? / 8.3.3：

Diophantine analysis / 8.4：

Quantum computation / 8.5：

Intuition on quantum Turing machines (QTMs) / 8.5.1：

The Shor quantum algorithm for factoring / 8.5.2：

Curious, anecdotal, and interdisciplinary references to primes / 8.6：

Fast Algorithms for Large-Integer Arithmetic / 8.7：

Tour of "grammar-school" methods / 9.1：

Multiplication / 9.1.1：

Squaring / 9.1.2：

Div and mod / 9.1.3：

Enhancements to modular arithmetic / 9.2：

Montgomery method / 9.2.1：

Newton methods / 9.2.2：

Moduli of special form / 9.2.3：

Exponentiation / 9.3：

Basic binary ladders / 9.3.1：

Enhancements to ladders / 9.3.2：

Enhancements for gcd and inverse / 9.4：

Binary gcd algorithms / 9.4.1：

Special inversion algorithms / 9.4.2：

Recursive-gcd schemes for very large operands / 9.4.3：

Large-integer multiplication / 9.5：

Karatsuba and Toom-Cook methods / 9.5.1：

Fourier transform algorithms / 9.5.2：

Convolution theory / 9.5.3：

Discrete weighted transform (DWT) methods / 9.5.4：

Number-theoretical transform methods / 9.5.5：

Schonhage method / 9.5.6：

Nussbaumer method / 9.5.7：

Complexity of multiplication algorithms / 9.5.8：

Application to the Chinese remainder theorem / 9.5.9：

Polynomial multiplication / 9.6：

Fast polynomial inversion and remaindering / 9.6.2：

Polynomial evaluation / 9.6.3：

Book Pseudocode / 9.7：

References

Preface

Primes! / 1：

Problems and progress / 1.1：

Fundamental theorem and fundamental problem / 1.1.1：

Technological and algorithmic progress / 1.1.2：

The infinitude of primes / 1.1.3：

続きを見る

東工大ブックレビュー

類似資料:

1 電子ブック Prime numbers and the Riemann hypothesis ((ebook)) Mazur, Barry, Stein, William A.	7 図書 Primality testing in polynomial time : from randomized algorithms to"primes is in P" Dietzfelbinger, Martin Springer
2 図書 Projects in scientific computation (: New York ; : Berlin) Crandall, Richard E., 1947- TELOS	8 図書 Primes of the form x[2] + ny[2] : Fermat, class field theory, and complex multiplication (: pbk) Cox, David A. Wiley
3 図書 The book of prime number records (: us ; : gw) Ribenboim, Paulo Springer-Verlag	9 電子ブック Primes of the form x[2] + ny[2] : Fermat, class field theory, and complex multiplication (: electronic bk) Cox, David A. Wiley Online Library
4 図書 The little book of big primes (: us ; : gw) Ribenboim, Paulo, 1928- Springer-Verlag	10 図書 Primes of the form x[2] + ny[2] : Fermat, class field theory, and complex multiplication (: pbk) Cox, David A. John Wiley & Sons
5 図書 The prime number theorem (: hbk ; : pbk) Jameson, G. J. O. Cambridge University Press	11 図書 Mathematica for the sciences Crandall, Richard E., 1947- Addison-Wesley, Advanced Book Program
6 図書 The development of prime number theory : from Euclid to Hardy and Littlewood Narkiewicz, Władysław Springer	12 図書 Pascal applications for the sciences (: pbk) Crandall, Richard E., 1947- Wiley