New Sparse Multivariate Polynomial Factorization Algorithms over Integers

DOI10.1145/3597066.3597087MaRDI QIDQ6060389

Qiao-Long Huang, Xiao-Shan Gao

Publication date: 3 November 2023

Published in: Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation (Search for Journal in Brave)

zbMATH Keywords

polynomial factorizationpolynomial complexitysparse multivariate polynomial

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Factors of low individual degree polynomials
• Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators
• Factoring sparse multivariate polynomials
• Irreducibility of multivariate polynomials
• Factoring polynomials with rational coefficients
• Factoring multivariate polynomials with many factors and huge coefficients
• The complexity of sparse Hensel lifting and sparse polynomial factorization
• Computing Frobenius maps and factoring polynomials
• On Hensel factorization. I
• Using Sparse Interpolation in Hensel Lifting
• Modern Computer Algebra
• Fast Polynomial Factorization and Modular Composition
• Effective Hilbert irreducibility
• Polynomial-Time Reductions from Multivariate to Bi- and Univariate Integral Polynomial Factorization
• A New Algorithm for Factoring Polynomials Over Finite Fields
• Factoring Multivariate Polynomials Over the Integers
• An Improved Multivariate Polynomial Factoring Algorithm
• Complexity issues in bivariate polynomial factorization
• Deterministic Factorization of Sparse Polynomials with Bounded Individual Degree
• On the complexity of factoring bivariate supersparse (Lacunary) polynomials
• Deterministically Factoring Sparse Polynomials into Multilinear Factors and Sums of Univariate Polynomials
• Factoring Polynomials Over Large Finite Fields