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

DOI10.1007/s00453-011-9500-yzbMath1236.68303arXiv1002.0739OpenAlexW2128365909MaRDI QIDQ2429362

Andrew Novocin, Mark van Hoeij

Publication date: 26 April 2012

Published in: Algorithmica, LATIN 2010: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1002.0739

zbMATH Keywords

polynomial factorizationalgorithmic complexitylattice reductionalgebraic number reconstructionknapsack lattices

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Symbolic computation and algebraic computation (68W30) Number-theoretic algorithms; complexity (11Y16) Algebraic number theory computations (11Y40)

Related Items

Computing sparse GCD of multivariate polynomials via polynomial interpolation ⋮ Towards faster polynomial-time lattice reduction ⋮ Lattice Reduction for Modular Knapsack ⋮ -adic images of Galois for elliptic curves over (and an appendix with John Voight) ⋮ Order bounds for C2-finite sequences ⋮ Odd degree isolated points on \(X_1(N)\) with rational \(j\)-invariant ⋮ Computing subfields of number fields and applications to Galois group computations ⋮ The complexity of computing all subfields of an algebraic number field ⋮ LLL for ideal lattices: re-evaluation of the security of Gentry-Halevi's FHE scheme ⋮ Efficient UC-Secure Authenticated Key-Exchange for Algebraic Languages ⋮ Isomorphisms of algebraic number fields

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Factoring polynomials and the knapsack problem
• Factoring polynomials over global fields
• Factoring polynomials with rational coefficients
• Small solutions to polynomial equations, and low exponent RSA vulnerabilities
• The optimal LLL algorithm is still polynomial in fixed dimension.
• A relative van Hoeij algorithm over number fields
• The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant
• H-LLL
• An LLL Algorithm with Quadratic Complexity
• Polynomial Factorization and Nonrandomness of Bits of Algebraic and Some Transcendental Numbers
• A more efficient algorithm for lattice basis reduction
• On the equidistribution of Hecke points
• Floating-Point LLL: Theoretical and Practical Aspects
• LLL: A Tool for Effective Diophantine Approximation
• Floating-Point LLL Revisited
• Lattice attacks on digital signature schemes