<p>I am interested in the computational complexity of the following problem.
Input: a polynomial p(x) with positive integer coefficients
Output: a factorization of p(x) into irreducible factors having positive integer coefficients themselves</p>

CC BY-SA 4.0
2021-12-28T15:27:27.030Z
This forum is for research level questions only. You should google for "LLL" (Lenstra, Lenstra and Lovász) or "Zassenhaus algorithm", or read a textbook on computer algebra (for instance the book by Von zur Gathen and Gerhard).
Gamow
CC BY-SA 4.0
2021-12-28T23:12:28.197Z
https://en.wikipedia.org/wiki/Factorization_of_polynomials
D.W.
CC BY-SA 4.0
2021-12-29T14:39:03.470Z
Thank you for your immediate reply, did you notice that I am not looking for algorithms that compute the factorization of elements of Z[x] but of elements of N[X] ... are you sure that LLL algorithms produce factors in N[x] ? I do not think so ... did you notice for example that over N[x] factorization is not unique ? ....
luciano
<polynomials><factoring>
Computational complexity of factoring univariate polynomials with positive integer coefficients
luciano
# Computational complexity of factoring univariate polynomials with positive integer coefficients

(Asked by: username_0 on 2021-12-28)

I am interested in the computational complexity of the following problem.
Input: a polynomial p(x) with positive integer coefficients
Output: a factorization of p(x) into irreducible factors having positive integer coefficients themselves

**Tags:** polynomials, factoring
> **Comments:**
> **username_1**: This forum is for research level questions only. You should google for "LLL" (Lenstra, Lenstra and Lovász) or "Zassenhaus algorithm", or read a textbook on computer algebra (for instance the book by Von zur Gathen and Gerhard).  
> **username_2**: https://en.wikipedia.org/wiki/Factorization_of_polynomials  
> **username_0**: Thank you for your immediate reply, did you notice that I am not looking for algorithms that compute the factorization of elements of Z[x] but of elements of N[X] ... are you sure that LLL algorithms produce factors in N[x] ? I do not think so ... did you notice for example that over N[x] factorization is not unique ? ....  

---

## 0 answers

