Gradual sub-lattice reduction and a new complexity for factoring polynomials

Mark Van Hoeij, Andrew Novocin

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 s…