Algorithmics and Lattices, some references

Lattices and Algorithmic Number Theory

Back to the main page

Factorization of polynomials:

Polynomial Factorization and Nonrandomness of Bits of Algebraic and Some Transcendental Numbers, STOC 1984, Kannan R. and Lenstra A. and Lovasz L. (1984)
Factoring Polynomials and the Knapsack Problem, Van Hoeij M. (2001)

Roots of modular polynomials:

How to Guess l-th Roots Modulo n by Reducing Lattice Bases, AAECC, Girault M. and Toffin P. and Vallée B. (1988)
Computation of Approximate L-th Roots Modulo n and Application to Cryptography, CRYPTO 1988, Girault M. and Toffin P. and Vallée B. (1988)
Finding a Small Root of a Bivariate Integer Equation; Factoring with High Bits Known, Coppersmith D. (1996)
Finding a Small Root of a Univariate Modular Equation, Coppersmith D. (1996)
Finding Small Roots of Univariate Modular Equations Revisited, IMA Int. Conf., Howgrave-Graham N. (1997)
Finding Small Solutions to Small Degree Polynomials, Coppersmith D. (2001)

Factorization of Integers:

Provably Fast Integer Factoring with Quasi-Uniform Small Quadratic Residues, STOC 1989, Vallée B. (1989)
Factoring Integers and Computing Discrete Logarithms via Diophantine Approximation, Schnorr C.P. (1993)
Factoring via Strong Lattice Reduction Algorithm, Ritter H. and Rössner C. (1997)
Factoring N=prq for large r , Boneh D. and Durfee G. and Howgrave-Graham N. (1999)

Linear Equations with Integer Coefficients:

Solving Simultaneous Modular Equations of Low Degree, Håstad J. (1988)
Polynomial Time algorithms for Finding Integer Relations among real Numbers, SIAM Journal on Computing, Vol.18, Håstad J. and Just B. and Lagarias J. and Schnorr C.P. (1989)
Solving a Linear Diophantine Equation with Lower and Upper Bounds on the Variables, Aardal K. and Hurkens C. and Lenstra A. (1998)
Hard Equality Constrained Integer Knapsacks, Lenstra A. and Aardal K. (2002)

Chinese remaindering: