Factoring polynomials and the knapsack problem

DOI10.1006/jnth.2001.2763zbMath1081.11080OpenAlexW2167708641MaRDI QIDQ701105

Mark van Hoeij

Publication date: 16 October 2002

Published in: Journal of Number Theory (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/6296ea8d15e29e3a73bd784e0eda18ad8ad3bb37

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Number-theoretic algorithms; complexity (11Y16) Polynomials, factorization in commutative rings (13P05)

Related Items (33)

Towards faster polynomial-time lattice reduction ⋮ Lifting and recombination techniques for absolute factorization ⋮ Decidability of Univariate Real Algebra with Predicates for Rational and Integer Powers ⋮ Computing with algebraically closed fields ⋮ A relative van Hoeij algorithm over number fields ⋮ Polynomial factorization algorithms over number fields ⋮ Iterated elliptic and hypergeometric integrals for Feynman diagrams ⋮ Modular Las Vegas algorithms for polynomial absolute factorization ⋮ A heuristic technique for decomposing multisets of non-negative integers according to the Minkowski sum ⋮ Order bounds for C2-finite sequences ⋮ \textsc{Rings}: an efficient Java/Scala library for polynomial rings ⋮ Gradual sub-lattice reduction and a new complexity for factoring polynomials ⋮ Formalizing the LLL basis reduction algorithm and the LLL factorization algorithm in Isabelle/HOL ⋮ Sparse bivariate polynomial factorization ⋮ Conquering inseparability: primary decomposition and multivariate factorization over algebraic function fields of positive characteristic ⋮ Factoring polynomials over global fields. II. ⋮ Fast computation of special resultants ⋮ A verified implementation of the Berlekamp-Zassenhaus factorization algorithm ⋮ Foreword ⋮ Complex spherical codes with three inner products ⋮ The numerical factorization of polynomials ⋮ New recombination algorithms for bivariate polynomial factorization based on Hensel lifting ⋮ Valuations of rational solutions of linear difference equations at irreducible polynomials ⋮ Factorization of Polynomials and GCD Computations for Finding Universal Denominators ⋮ Isomorphisms of algebraic number fields ⋮ LLL: A Tool for Effective Diophantine Approximation ⋮ The van Hoeij Algorithm for Factoring Polynomials ⋮ Using LLL-Reduction for Solving RSA and Factorization Problems ⋮ Integral Representation and Algorithms for Closed Form Summation ⋮ Primary decomposition of zero-dimensional ideals over finite fields ⋮ On the rational summation problem ⋮ Factoring polynomials over global fields ⋮ Random lattices, threshold phenomena and efficient reduction algorithms.

Uses Software

• Magma
• Maple
• NTL

Cites Work

• Solving exponential diophantine equations using lattice basis reduction algorithms
• A unified method for multivariate polynomial factorizations
• Factoring polynomials with rational coefficients
• Lattice basis reduction: Improved practical algorithms and solving subset sum problems
• The Magma algebra system. I: The user language
• Factorization of differential operators with rational functions coefficients
• On Hensel factorization. I
• Factorization in Z[x]
• An Inequality About Factors of Polynomials
• Analysis of PSLQ, an integer relation finding algorithm
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Factoring polynomials and the knapsack problem