Gradual Sub‐lattice Reduction and a New Complexity for Factoring Polynomials

We present a lattice algorithm specifically designed for some classical applications of lattice reduction. The applications are for lattice bases with a generalized knapsack‐type structure, where the target vectors have bounded depth. For such applications, the complexity of the algorithm improves traditional lattice reduction by replacing some dependence on the bit‐length of the input vectors by some dependence on the bound for the output vectors. If the bit‐length of the target vectors is unrelated to the bit‐length of the input, then our algorithm is only linear in the bit‐length of the input entries, which is an improvement over the quadratic complexity floating‐point LLL algorithms. To illustrate the usefulness of this algorithm we show that a direct application to factoring univariate polynomials over the integers leads to the first complexity bound improvement since 1984. A second application is algebraic number reconstruction, where a new complexity bound is obtained as well.