PAPERS OF INTEREST: ALGORITHMIC NUMBER THEORY

Caveat: Reference details are often incomplete.
  1. Discrete Logarithm

    1. B. A. LaMacchia and A. M. Odlyzko, Computation of Discrete Logarithms in Prime Fields, manuscript

    2. A. M. Odlyzko, Discrete Logarithms and Smooth Polynomials, Contemporary Mathematics

    3. A. M. Odlyzko, On the Complexity of Computing Discrete Logarithms and Factoring Integers, manuscript

  2. General Algorithmic Number Theory

    1. Leonard M. Adleman and Kevin S. McCurley, Open Problems in Number Theoretic Complexity, Discrete Algorithms and Complexity, 1987, 237-261

    2. Leonard M. Adleman and Kevin S. McCurley, Open Problems in Number Theoretic Complexity, II, Algorithmic Number Theory, ANTS-I, 1994, 291-322

    3. H. W. Lenstra, Jr., Elliptic Curves and Number-Theoretic Algorithms, Proceeding of the International Congress of Mathematicians, 1987, 99-120

  3. Greatest Common Divisor

    1. David Ford and George Havas, A New Algorithm and Refined Bounds for Extended GCD Computation, Algorithmic Number Theory, ANTS-I, 1994, 145-150

    2. Bohdan S. Majewski and George Havas, The Complexity of Greatest Common Divisor Computations, Algorithmic Number Theory, ANTS-I, 1994, 184-193

    3. Jeffrey Shallit and Jonathan Sorenson, Analysis of a Left-Shift Binary GCD Algorithm, Algorithmic Number Theory, ANTS-I, 1994, 169-183

    4. Jeffrey Shallit and Jonathan Sorenson, Analysis of a Left-Shift Binary GCD Algorithm, Journal of Symbolic Computation 17, 1994, 473-486

  4. Integer Factorization

    1. Leonard M. Adleman, The Function Field Sieve, Algorithmic Number Theory, ANTS-I, 1994, 108-121

    2. D. H. Lehmer, Factorization Then and Now, Computers in Mathematics, 1990, 311-320

    3. Arjen K. Lenstra, Factoring Integers Using the Web and the Number Field Sieve, manuscript, September 15, 1995

    4. H. W. Lenstra, Jr., Factoring Integers With Elliptic Curves, Annals of Mathematics 126, 1987, 649-673

    5. James McKee and Richard Pinch, Old and New Deterministic Factoring Algorithms, Algorithmic Number Theory, ANTS-I, 1994, 217-224

    6. Andrew M. Odlyzko, The Future of Integer Factorization, manuscript, July 11, 1995

    7. Carl Pomerance, Fast, Rigorous Factorization and Discrete Logarithm Algorithms, Discrete Algorithms and Complexity, 1987, 119-143

  5. Lattice Basis Reduction

    1. L. Babai, On Lovasz' Lattice Reduction and the Nearest Lattice Point Problem, Combinatorica 6, 1986, 1-13

    2. Matthius J. Coster, Antoine Joux, Brian A. LaMacchia, Andrew M. Odlyzko, Claus-Peter Schnorr, and Jacques Stern, Improved Low-Density Subset Sum Algorithms, Computational Complexity 2, 1992, 111-128

    3. Ravi Kannan, Lattices, Basis Reduction and the Shortest Vector Problem, Theory of Algorithms, L. Lovasz nd E. Szemeredi, editors, 1984, 283-311

    4. Ravi Kannan, Minkowski's Convex Body Theorem and Integer Programming, Mathematics of Operations Research 12, 1987, 415-440

    5. A. K. Lenstra, H. W. Lenstra, Jr., and L. Lovasz, Factoring Integers with Rational Coefficients, Mathematische Annalen 261, 1982, 515-534

    6. Oded Goldreich, Shafi Goldwasser, and Shai Halevi, Public-Key Cryptosystems from Lattice Reduction Problems, ECCC TR96-056, 1996

    7. Oded Goldreich and Shafi Goldwasser, On the Limits of Non-Approximability of Lattice Problems, ECCC TR97-031, 1997

    8. C. P. Schnorr and M. Euchner, Lattice Basis Reduction: Improved Practical Algorithms and Solving Subset Sum Problems, Fundamentals of Computation Theory, FCT '91, LNCS no. 529, 1991, 68-85

  6. Polynomial Factorization

    1. Erich Kaltofen, Polynomial Factorization 1982-1986, Computer in Mathematics, 1990

    2. Susan Landau, Factoring Polynomials over Algebraic Number Fields, SIAM Journal on Computing 14, 1985, 184-195

    3. Joachim von zur Gathen and Daniel Panario, Factoring Polynomials over Finite Fields: A Survey, Technical Report 97-183, University of Paderborn, 1997

  7. Primality Testing

    1. Arjen K. Lenstra, Primality Tesing, Cryptology and Computational Number Theory, 1990

    2. Paul Pritchard, Improved Incremental Prime Number Sieves, Algorithmic Number Theory, ANTS-I, 1994, 280-288

Please report any problems found in these pages to:

CS6104 EI Account (cs6104@ei.cs.vt.edu)