Fast separable factorization and applications

DOI10.1007/s00200-008-0062-4zbMath1205.12008OpenAlexW2055223395MaRDI QIDQ2426955

Grégoire Lecerf

Publication date: 14 May 2008

Published in: Applicable Algebra in Engineering, Communication and Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00200-008-0062-4

zbMATH Keywords

Irreducible factorizationPolynomial factorizationSeparable factorizationSquarefree factorization

Mathematics Subject Classification ID

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

Related Items

Reduction of bivariate polynomials from convex-dense to dense, with application to factorizations, Algebraic diagonals and walks: algorithms, bounds, complexity, Deterministic root finding over finite fields using Graeffe transforms, Bivariate factorization using a critical fiber, Univariate polynomial factorization over finite fields with large extension degree, A note on Gao's algorithm for polynomial factorization, Complexity bounds for the rational Newton-Puiseux algorithm over finite fields, Factoring bivariate polynomials using adjoints, Polynomial root finding over local rings and application to error correcting codes, Sparse bivariate polynomial factorization, On the complexity of the Lickteig-Roy subresultant algorithm, New recombination algorithms for bivariate polynomial factorization based on Hensel lifting, Exact bivariate polynomial factorization over \(\mathbb Q\) by approximation of roots

Uses Software

• Magma

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• New recombination algorithms for bivariate polynomial factorization based on Hensel lifting
• Factoring polynomials over global fields
• Separability and factoring polynomials
• A course in constructive algebra
• On square-free factorization of multivariate polynomials over a finite field.
• Square-free algorithms in positive characteristic
• Conquering inseparability: primary decomposition and multivariate factorization over algebraic function fields of positive characteristic
• Improved dense multivariate polynomial factorization algorithms
• On the factorization of polynomials in a finite number of steps
• Constructions in a Polynomial Ring Over the Ring of Integers
• Effective procedures in field theory
• Sharp precision in Hensel lifting for bivariate polynomial factorization
• Hensel and Newton Methods in Valuation Rings
• Constructions in Algebra
• Square-free decomposition in finite characteristic
• Construction of the integral closure of a finite integral domain
• Fast modular algorithms for squarefree factorization and Hermite integration
• Absolute irreducibility of polynomials via Newton polytopes