Algorithmic Number Theory

1. Front Matter

   PDF

2. On the difficulty of finding reliable witnesses

   • W. R. Alford, Andrew Granville, Carl Pomerance

   Pages 1-16

3. Density computations for real quadratic 2-class groups

   • Wieb Bosma, Peter Stevenhagen

   Pages 17-17

4. Lattice sieving and trial division

   • Roger A. Golliver, Arjen K. Lenstra, Kevin S. McCurley

   Pages 18-27

5. A subexponential algorithm for discrete logarithms over the rational subgroup of the Jacobians of large genus hyperelliptic curves over finite fields

   • Leonard M. Adleman, Jonathan DeMarrais, Ming-Deh Huang

   Pages 28-40

6. Computing rates of growth of division fields on CM Abelian varieties

   • Bruce A. Dodson, Matthew J. Haines

   Pages 41-41

7. Algorithms for CM-Fields

   • Sachar Paulus

   Pages 42-42

8. Schoof's algorithm and isogeny cycles

   • Jean-Marc Couveignes, François Morain

   Pages 43-58

9. Integer points on rational elliptic curves

   • Nelson Stephens

   Pages 59-59

10. Counting the number of points on elliptic curves over finite fields of characteristic greater than three

    • Frank Lehmann, Markus Maurer, Volker Müller, Victor Shoup

    Pages 60-70

11. Straight-line complexity and integer factorization

    • Richard J. Lipton

    Pages 71-79

12. Decomposition of algebraic functions

    • Dexter Kozen, Susan Landau, Richard Zippel

    Pages 80-92

13. A new modular interpolation algorithm for factoring multivariate polynomials

    • Ronitt Rubinfeld, Richard Zippel

    Pages 93-107

14. The function field sieve

    • Leonard M. Adleman

    Pages 108-121

15. Heegner point computations

    • Noam D. Elkies

    Pages 122-133

16. Computing the degree of a modular parametrization

    • J. E. Cremona

    Pages 134-142

17. Galois representations from the cohomology of SL(3,ℤ)

    • Mark McConnell

    Pages 143-143

18. An analysis of the Gaussian algorithm for lattice reduction

    • Hervé Daudé, Philippe Flajolet, Brigitte Vallée

    Pages 144-158

19. A fast variant of the Gaussian reduction algorithm

    • Michael Kaib

    Pages 159-159

20. Reducing lattice bases by means of approximations

    • Johannes Buchmann

    Pages 160-168

This volume presents the refereed proceedings of the First Algorithmic Number Theory Symposium, ANTS-I, held at Cornell University, Ithaca, NY in May 1994.
The 35 papers accepted for inclusion in this book address many current issues of algorithmic, computational and complexity-theoretic aspects of number theory and thus report the state-of-the-art in this exciting area of research; the book also contributes essentially to foundational research in cryptology and coding.
Of particular value is a collection entitled "Open Problems in Number Theoretic Complexity, II" contributed by Len Adleman and Kevin McCurley. This survey presents on 32 pages 36 central open problems and relates them to the literature by means of some 160 references.

• Finite Fields
• Greatest Common Divisor (GCD)
• Größtter Gemeinsamer Teiler
• Integer Factorization
• Number theory
• Polynom-Faktorisierung
• Polynominal Factorization
• Siebmethoden
• Sieve Methods
• algorithms
• ants
• complexity
• data structures
• algorithm analysis and problem complexity
• combinatorics

Policies and ethics