2024/10/21 by Shahriar Iravanian, Iravanian, Shahriar
Computer Science · #05-08 #12-08 #Computational Complexity (cs.CC) #F.2.2 #FOS: Computer and information sciences #I.1.1 #I.1.2 #Matrix Theory and Algorithms #Polynomial and algebraic computation #Symbolic Computation (cs.SC)
paper · pdf · doi:10.48550/arxiv.2410.15880
openalex publication_date 2024/10/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Polynomial factorization over ZZ is of great historical and practical importance. Currently, the standard technique is to factor the polynomial over finite fields first and then to lift to integers. Factorization over finite fields can be done in polynomial time using Berlekamp or Cantor-Zassenhaus algorithms. Lifting from the finite field to ZZ requires a combinatorial algorithm. The van Hoeij algorithm casts the combinatorial problem as a knapsack-equivalent problem, which is then solved using lattice-reduction (the LLL algorithm) in polynomial time, which is implemented in many computer algebra systems (CAS). In this paper, we revisit the old idea of starting with factorization over RR instead of a finite field, followed by recombination of the resulting linear and quadratic factors. We transform the problem into an integer subset sum problem, which is then solved using the Horowizt-Sinha algorithm. This algorithm can factor a random integer polynomial of degree d in a time complexity of O(2^(d slash 4)). While the resulting algorithm is exponential, consistent with the integer subset sum problem being in NP, it has a few advantages. First, it is simple and easy to implement. Second, it is almost embarrassingly parallelizable. We demonstrate this by implementing the algorithm in a Graphic Processing Unit (GPU). The resulting code can factor a degree 100 polynomial is a few tenths of a second, comparable to some standard CAS. This shows that it is possible to use current hardware, especially massively parallel systems like GPU, to the benefit of symbolic algebra.