Primes and the Beauty of Algorithms

The algorithmical problem of distinguishing primes from composites is both a simple and fascinating problem in number theory. The discovery of a polynomial deterministic algorithm for proving primality addressed this problem from a complexity theory point of view, but practical problems remain. This book is one of the first to comprehensively cover the Agrawal-Kayal-Saxena test for proving primality. Focusing on three current algorithms to illustrate general primality proving, the text presents the necessary background for understanding the common framework behind all primality proving algorithms and demonstrates how theoretical gains often occur at the expense of practical advantages.