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

  • $\begingroup$ 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). $\endgroup$
    – Gamow
    Dec 28 '21 at 15:27
  • 1
    $\begingroup$ en.wikipedia.org/wiki/Factorization_of_polynomials $\endgroup$
    – D.W.
    Dec 28 '21 at 23:12
  • $\begingroup$ 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 ? .... $\endgroup$
    – luciano
    Dec 29 '21 at 14:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.