From ACM Distinguished Dissertation

Analytic Methods in the Analysis and Design of Number Theoretic Algorithms

By Eric Bach

Overview

Author(s)

Summary

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.

Hardcover

Out of Print ISBN: 9780262022194 50 pp. | 7 in x 9 in