Algorithmic Number Theory: Efficient algorithms, Band 1MIT Press, 1996 - 512 Seiten Algorithmic Number Theory provides a thorough introduction to the design and analysis of algorithms for problems from the theory of numbers. Although not an elementary textbook, it includes over 300 exercises with suggested solutions. Every theorem not provided in the text or left as an exercise has a reference in the notes section that appears at the end of each chapter. The bibliography contains over 1750 citations to the literature. Finally, it blends computational theory with practice by covering some of the practical aspects of algorithm implementations. |
Inhalt
Introduction | 1 |
Intractable Problems will cover the following topics | 3 |
Fundamentals of Number Theory | 19 |
A Survey of Complexity Theory | 41 |
The Greatest Common Divisor | 67 |
Computing in Zn | 101 |
Finite Fields | 125 |
Solving Equations over Finite Fields | 155 |
Discrete Logarithms | 162 |
Open Problems | 194 |
Facts and Heuristics | 203 |
Basic Algorithms | 265 |
A Solutions to Exercises | 319 |
Andere Ausgaben - Alle anzeigen
Algorithmic Number Theory: Efficient Algorithms Eric Bach,Jeffrey Shallit Keine Leseprobe verfügbar - 1996 |
Algorithmic Number Theory: Efficient algorithms, Band 1 Eric Bach,Jeffrey Outlaw Shallit Keine Leseprobe verfügbar - 1996 |
Algorithmic Number Theory: Efficient Algorithms, Band 1 Eric Bach,Jeffrey Shallit Keine Leseprobe verfügbar - 1996 |
Häufige Begriffe und Wortgruppen
a₁ algebraic number Amer arithmetic Assume ERH asymptotic binary bit operations bound Carmichael numbers Chapter Chinese remainder theorem coefficients Comp compute congruences conjecture continued fraction D. H. Lehmer defined deterministic polynomial discussed element equation Erdős estimate Euclidean algorithm Euler example Exercise Fermat's finite fields formula Gathen gcd(a given greatest common divisor H. W. Lenstra Hence input irreducible polynomial L₁ Lemma li(x linear log log Lucas machine Math Mersenne method mod f modulo monic polynomial multiplication nonzero NP-complete number field number of primes number theory O(lg Odlyzko polynomial-time Pomerance positive integers primality testing prime factorization prime number theorem primitive root probabilistic problem proof proved pseudoprime quadratic nonresidue randomized algorithm relatively prime result Riemann hypothesis ring root of unity running Show sieve solution square roots squarefree steps u₁ x₁ zeroes zeta function