Prime Numbers : A Computational Perspective / by Richard Crandall, Carl Pomerance
| データ種別 | 電子ブック |
|---|---|
| 出版者 | New York, NY : Springer New York |
| 出版年 | 2001 |
| 本文言語 | 英語 |
| 大きさ | XV, 547p : online resource |
書誌詳細を非表示
| 内容注記 | 1 Primes! 1.1 Problems and progress 1.2 Celebrated conjectures and curiosities 1.3 Primes of special form 1.4 Analytic number theory 1.5 Exercises 1.6 Research problems 2 Number-Theoretical Tools 2.1 Modular arithmetic 2.2 Polynomial arithmetic 2.3 Squares and roots 2.4 Exercises 2.5 Research problems 3. Recognizing Primes and Composites 3.1 Trial division 3.2 Sieving 3.3 Pseudoprimes 3.4 Probable primes and witnesses 3.5 Lucas pseudoprimes 3.6 Counting primes 3.7 Exercises 3.8 Research problems 4. Primality Proving 4.1 The n - 1 test 4.2 The n + 1 test 4.3 The finite field primality test 4.4 Gauss and Jacobi sums 4.5 Exercises 4.6 Research problems 5 Exponential Factoring Algorithms 5.1 Squares 5.2 Monte Carlo methods 5.3 Baby-steps, giant-steps 5.4 Pollard p — 1 method 5.5 Polynomial evaluation method 5.6 Binary quadratic forms 5.7 Exercises 5.8 Research problems 6 Subexponential Factoring Algorithms 6.1 The quadratic sieve factorization method 6.2 Number field sieve 6.3 Rigorous factoring 6.4 Index-calculus method for discrete logarithms 6.5 Exercises 6.6 Research problems 7. Elliptic Curve Arithmetic 7.1 Elliptic curve fundamentals 7.2 Elliptic arithmetic 7.3 The theorems of Hasse, Deuring, and Lenstra 7.4 Elliptic curve method 7.5 Counting points on elliptic curves 7.6 Elliptic curve primality proving (ECPP) 7.7 Exercises 7.8 Research problems 8. The Ubiquity of Prime Numbers 8.1 Cryptography 8.2 Random-number generation 8.3 Quasi-Monte Carlo (qMC) methods 8.4 Diophantine analysis 8.5 Quantum computation 8.6 Curious, anecdotal, and interdisciplinary references to primes 8.7 Exercises 8.8 Research problems 9 Fast Algorithms for Large-Integer Arithmetic 9.1 Tour of “grammar-school” methods 9.2 Enhancements to modular arithmetic 9.3 Exponentiation 9.4 Enhancements for gcd and inverse 9.5 Large-integer multiplication 9.6 Polynomial arithmetic 9.7 Exercises 9.8 Research problems Book Pseudocode References |
|---|---|
| 一般注記 | In this volume we have endeavored to provide a middle ground-hopefully even a bridge-between "theory" and "experiment" in the matter of prime numbers. Of course, we speak of number theory and computer experiment. There are great books on the abstract properties of prime numbers. Each of us working in the field enjoys his or her favorite classics. But the experimental side is relatively new. Even though it can be forcefully put that computer science is by no means young, as there have arguably been four or five computer "revolutions" by now, it is the case that the theoretical underpinnings of prime numbers go back centuries, even millennia. So, we believe that there is room for treatises based on the celebrated classical ideas, yet authored from a modern computational perspective. Design and scope of this book The book combines the essentially complementary areas of expertise of the two authors. (One author (RC) is more the computationalist, the other (CP) more the theorist. ) The opening chapters are in a theoretical vein, even though some explicit algorithms are laid out therein, while heavier algorithmic concentration is evident as the reader moves well into the book. Whether in theoretical or computational writing mode, we have tried to provide the most up-to-date aspects of prime-number study. What we do not do is sound the very bottom of every aspect |
| 著者標目 | *Crandall, Richard author Pomerance, Carl author SpringerLink (Online service) |
| 件 名 | LCSH:Mathematics LCSH:Number theory FREE:Mathematics FREE:Number Theory |
| 分 類 | DC23:512.7 |
| 巻冊次 | ISBN:9781468493160 
|
| ISBN | 9781468493160 |
| URL | http://dx.doi.org/10.1007/978-1-4684-9316-0 |
目次／あらすじ