Computer Science – Symbolic Computation
Scientific paper
2010-02-03
in Gradual sub-lattice reduction and a new complexity for factoring polynomials - LATIN 2010, Oaxaca : Mexico (2010)
Computer Science
Symbolic Computation
Scientific paper
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 are boundably short. 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.
Hoeij Mark van
Novocin Andrew
No associations
LandOfFree
Gradual sub-lattice reduction and a new complexity for factoring polynomials does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Gradual sub-lattice reduction and a new complexity for factoring polynomials, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Gradual sub-lattice reduction and a new complexity for factoring polynomials will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-602138