Can I read Integer Polynomial Factorization by Recombination of Real Factors: Re-evaluating an Old Technique in Modern Era on EtoBox?

Integer Polynomial Factorization by Recombination of Real Factors: Re-evaluating an Old Technique in Modern Era by Iravanian, Shahriar is a scholarly article available to read on EtoBox.

What is Integer Polynomial Factorization by Recombination of Real Factors: Re-evaluating an Old Technique in Modern Era about?

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 imp

Author

Iravanian, Shahriar

Published

2024

Language

EN