An efficient sparse adaptation of the polytope method over F_q and a record-high binary bivariate factorisation

DOI10.1016/J.JSC.2007.10.011MaRDI QIDQ2482628zbMATH OpenOpenAlexFDO

Authors Fatima K. Abu Salem

Publication date 23 April 2008

Published in Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jsc.2007.10.011

zbMATH Keywords

finite fieldsNewton polytopesbivariate polynomialsfactorisationsparse polynomials

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Polynomials over finite fields (11T06) Number-theoretic algorithms; complexity (11Y16) Nonlinear algebraic or transcendental equations (65H99)

Recommendations

• Factoring polynomials via polytopes
• Factoring sparse bivariate polynomials using the priority queue
• Factoring bivariate sparse (lacunary) polynomials
• Reduction of bivariate polynomials from convex-dense to dense, with application to factorizations
• Sparse bivariate polynomial factorization

Cites work

• scientific article; zbMATH DE number 3976197 (Why is no real title available?)
• scientific article; zbMATH DE number 4032498 (Why is no real title available?)
• scientific article; zbMATH DE number 1552584 (Why is no real title available?)
• scientific article; zbMATH DE number 3893304 (Why is no real title available?)
• Absolute irreducibility of polynomials via Newton polytopes
• An Improved Multivariate Polynomial Factoring Algorithm
• An efficient algorithm for determining the convex hull of a finite planar set
• Complexity issues in bivariate polynomial factorization
• Computational Geometry in C
• Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators
• Decomposition of polytopes and polynomials
• Factoring Multivariate Polynomials Over the Integers
• Factoring Multivariate Polynomials over Algebraic Number Fields
• Factoring multivariate integral polynomials
• Factoring multivariate polynomials over finite fields
• Factoring multivariate polynomials via partial differential equations
• Factoring polynomials via polytopes
• Factoring sparse multivariate polynomials
• Hensel lifting and bivariate polynomial factorisation over finite fields
• Multivariate Polynomial Factorization
• On fast multiplication of polynomials over arbitrary algebras
• On the computational power of pushdown automata
• Polynomial-Time Reductions from Multivariate to Bi- and Univariate Integral Polynomial Factorization

Cited in

(6)

• Factoring sparse bivariate polynomials using the priority queue
• Tropical algebraic geometry in Maple: a preprocessing algorithm for finding common factors for multivariate polynomials with approximate coefficients
• An empirical study of cache-oblivious polygon indecomposability testing
• Exact bivariate polynomial factorization over \(\mathbb Q\) by approximation of roots
• Parallel methods for absolute irreducibility testing
• Sparse bivariate polynomial factorization

This page was built for publication: An efficient sparse adaptation of the polytope method over \(\mathbb F_q\) and a record-high binary bivariate factorisation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2482628)