We aim to factor a sparse polynomial a ∈ Z[ x 1 , ···, x n ] represented by a black box. The authors have previously developed efficient sparse Hensel lifting algorithms for the monic and square-free case that outperforms the algorithm by Kaltofen and Trager in 1990. We complete this black box factorization problem for the non-monic case with a new algorithm that computes the factors of a using many non-monic bivariate Hensel lifts. Our algorithm handles all cases of input a ∈ Z[ x 1 , ···, x n ] including the non-square-free and the non-primitive cases. We have implemented the algorithm in Maple with all major subroutines coded in C for efficiency.

Tian Chen

Factoring non-monic polynomials represented by black boxes

ivySCI AI Smartly Parses PDF, Answers Researchers' Questions, and Helps You Understand Papers in Seconds

Journal Info

Category	Quartile
MATHEMATICS, APPLIED	4