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.

  • 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 '13 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$ – 1.. Jun 29 '13 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 '13 at 14:40
  • $\begingroup$ @Bruno, if the polynomial is primitive, I believe LLL takes cares of factoring in poly time. Am I correct? $\endgroup$ – 1.. Jun 29 '13 at 14:45
  • $\begingroup$ True. It seemed to me that you were trying to avoid LLL. What I suggested is that the older factoring algorithms that run in exponential time in the worst case because of the reconstruction of the factors may yield polytime irreducibility tests. But that's only a suggestion! $\endgroup$ – Bruno Jun 29 '13 at 15:18

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.