This book makes a substantial contribution to the understanding of a murky area of number theory that is important to computer science, an area relevant to the design and analysis of number-theoretic algorithms and to the construction of cryptographic protocols.
Contents
Introduction • 1: Explicit Bounds for Primality Testing • Ankeny's Theorem and its Algorithmic Consequences • Background from Analytic Number Theory • Roots • Asymptotic Theorems • Zeta-function Estimates • Numerical Theorems • Computing Bounds for Specific Moduli • Comparisons with Empirical Results • 2: The Generation of Random Factorizations • Introduction • A Method That Almost Works • Doctoring the Odds • A Factor Generation Procedure • The Complete Algorithm • 2.5 Bounds for the Number of Prime Tests • A Single-precision Time Bound • The Use of Probabilistic Primality Tests
Analytic Methods in the Analysis and Design of Number Theoretic Algorithms is a 1984 ACM Distinguished Dissertation.