A Computational Perspective
Prime numbers belong to an exclusive world of intellectual conceptions. They are one of those marvelous notions that enjoy simple, elegant descriptions, yet lead to extreme complexity in the details. The basic notion of primality can be accessible to a child, yet no human mind harbors anything like a complete picture. In this book the authors concentrate on the computational aspect of finding and characterizing primes, but will often digress into the theoretical domain in order to illuminate, justify, and underscore the practical import of the computational algorithms. The book will be an indispensable reference for professionals interested in prime numbers and encryption, cryptography, factoring algorithms, elliptic curve arithmetic, and many more computational issues related to primes and factoring. Readers can test their understanding at the end of each chapter with a variety of exercises ranging from very easy to extremely difficult.
|Chapter 2:||NUMBER-THEORETICAL TOOLS|
|Chapter 3:||RECOGNIZING PRIMES AND COMPOSITES|
|Chapter 4:||PRIMALITY PROVING|
|Chapter 5:||EXPONENTIAL FACTORING ALGORITHMS|
|Chapter 6:||SUBEXPONENTIAL FACTORING ALGORITHMS|
|Chapter 7:||ELLIPTIC CURVE ARITHMETIC|
|Chapter 8:||THE UBIQUITY OF PRIME NUMBERS|
|Chapter 9:||FAST ALGORITHMS FOR LARGE-INTEGER ARITHMETIC|
PrimeKit — for Mathematica
The Crandall/Pomerance book above has 112 (one hundred twelve) algorithms cast explicitly in pseudocode. PrimeKit contains an implementation — as Mathematica source — of every one of the algorithms. Because these algorithm sources are designed for pedagogical strength (the code is clear & tutorial, as opposed to heavily-optimized), there is an "Extras" folder containing some efficient number-theoretical C sources, again in support of the Crandall/Pomerance book.
PrimeKit and multiple other software packages can be download from the free software page.