20
$\begingroup$

It is well known LLL algorithm provides a fully polynomial algorithm to factor a reducible primitive polynomial over $\mathbb{Z}[x]$.

Say one only seeks to identify whether a given polynomial over $\mathbb{Z}[x]$ is reducible, then what are the best ways known to solve this? If reducible, the algorithm should correctly say yes and if not, it should say no.

Improve this question
$\endgroup$
14
  • 3
    $\begingroup$ It doesn't work in all cases (i.e. this is not a general purpose algorithm), but in my research, I have been able to show that certain polynomials over $\mathbb{Z}$ are irreducible because the same polynomials are irreducible when viewed as polynomials over $\mathbb{F}_p$ for some prime $p$. $\endgroup$
    – Tyson Williams
    Jun 29, 2013 at 1:19
  • $\begingroup$ @TysonWilliams most cases I have seen is confirming irreducibility. That is if the polynomial is irreducible it gives yes. However if reducible, the algorithm does not output reducible. Is there a reducibility test that works in poly time without LLL for primitive polynomials? $\endgroup$
    – Turbo
    Jun 29, 2013 at 7:26
  • $\begingroup$ I do not have the answer, but there may be some possibilities using Hensel lifting, as in Zassenhaus algorithm. This algorithm (to factor integral polynomials) can be exponential because of a combinatorial explosion during the reconstruction phase. There may be a way to avoid this explosion if you do not need to really reconstruct the factors. $\endgroup$
    – Bruno
    Jun 29, 2013 at 14:40
  • $\begingroup$ @Bruno, if the polynomial is primitive, I believe LLL takes cares of factoring in poly time. Am I correct? $\endgroup$
    – Turbo
    Jun 29, 2013 at 14:45
  • 1
    $\begingroup$ @JoshuaGrochow The equivalence in Kopparty-Saraf-Shpilka is as follows: Univariate factoring + Efficient PIT is equivalent to Multivariate factoring. Roughly speaking, the randomized steps in the reduction from multivariate to univariate factoring are derandomized using the PIT oracle in that paper. Since this question is for univariates only, I don't think that paper helps here. Moreover, PIT for univariate polynomials is trivial, so I don't see PIT helping here. $\endgroup$
    – Pranav Bisht
    Jul 7, 2021 at 10:16

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.