Office of Academic Resources
Chulalongkorn University
Chulalongkorn University

Home / Help

AuthorCrandall, Richard. author
TitlePrime Numbers [electronic resource] : A Computational Perspective / by Richard Crandall, Carl Pomerance
ImprintNew York, NY : Springer New York, 2001
Connect tohttp://dx.doi.org/10.1007/978-1-4684-9316-0
Descript XV, 547p. online resource

SUMMARY

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


CONTENT

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 โ{128}{148} 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 โ{128}{156}grammar-schoolโ{128}{157} 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


Mathematics Number theory Mathematics Number Theory



Location



Office of Academic Resources, Chulalongkorn University, Phayathai Rd. Pathumwan Bangkok 10330 Thailand

Contact Us

Tel. 0-2218-2929,
0-2218-2927 (Library Service)
0-2218-2903 (Administrative Division)
Fax. 0-2215-3617, 0-2218-2907

Social Network

  line

facebook   instragram