3 ms·
>> Lattice reduction techniques give a polynomial algorithm to factor polynomials with integral coefficients (does the polynomial factor into other polynomials
by phkahler 5y ago
>> Lattice reduction techniques give a polynomial algorithm to factor polynomials with integral coefficients (does the polynomial factor into other polynomials with integral coefficients)
Wait, are you saying factorization of polynomials is in P? That doesn't feel right since factoring integers has not been shown to be in P (yet).
- abetusk 5y agoYes, that's what I'm saying. Factoring univariate polynomials with integer coefficients (that is, seeing if a polynomial with integer coefficients has smaller degree polynomial factors with integer coefficients) is in P [0]. Factoring univariate polynomials over the integers has known to be in P since the 1980s (since LLL came out, which is one of the major reasons why LLL was developed in the first place). Integer factorization is still currently unknown to be in P or not in P. If you see how to use polynomial factoring to factor integers, please let me know. [0] https://en.wikipedia.org/wiki/Factorization_of_polynomials#Factoring_univariate_polynomials_over_the_integers https://en.wikipedia.org/wiki/Factorization_of_polynomials#F...