20

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.

Joshua Grochow
  • 37,260
  • 4
  • 129
  • 228
Turbo
  • 12,812
  • 1
  • 19
  • 68
  • 3
    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$. – Tyson Williams Jun 29 '13 at 01:19
  • @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? – Turbo Jun 29 '13 at 07:26
  • 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. – Bruno Jun 29 '13 at 14:40
  • @Bruno, if the polynomial is primitive, I believe LLL takes cares of factoring in poly time. Am I correct? – Turbo Jun 29 '13 at 14:45
  • 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! – Bruno Jun 29 '13 at 15:18
  • I want to avoid LLL since I am only looking for a test for reducibility. – Turbo Jun 29 '13 at 15:29
  • (afaik) isnt this closely connected to polynomial identity testing? for which there is a large body of research and ongoing/ active investigation, it also has strong/ deep connections to open complexity class separations. fyi wikipedia entry on LLL algorithm – vzn Mar 30 '15 at 16:49
  • @vzn How is deciding $f(x)\in\Bbb Z[x]$ splits in $\Bbb Z[x]$ related to PIT? Problem seems simpler than actual splitting. – Turbo Mar 30 '15 at 19:38
  • the general idea is a connection between factoring and testing equivalence of two polynomials. just turned this up, maybe have seen this ref before, not sure. Equivalence of Polynomial Identity Testing and Deterministic Multivariate Polynomial Factorization Kopparty, Saraf, Shpilka – vzn Mar 30 '15 at 20:35
  • @vzn I apologize it is still unclear to me what exactly connection is. – Turbo Mar 30 '15 at 23:56
  • For polys given by circuits/black boxes (I know, not the usual setting of eg LLL, which is why this isn't really an answer...), this is PIT-complete, following up on vzn's suggestion. Given f, make a new circuit that is $g=f \cdot x$ of nearly the same size. Then $g$ is irreducible iff $g=f=0$, so you can decide if $f =0$ using an irreducibility test. In the other direction, use Kopparty-Saraf-Shpilka to use PIT to factor f, then f was irreducible iff it only had one factor. – Joshua Grochow Apr 10 '21 at 02:26
  • (Sry g and f could be irreducible if f is any constant. So even if g is irreducible, one then needs to evaluate g at any two points, say 0,1, to see if it's identically zero or not.) – Joshua Grochow Apr 10 '21 at 02:40
  • 1
    @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. – Pranav Bisht Jul 07 '21 at 10:16
  • @1.. Since this question is quite old, kindly let me know if you got an answer to your question. I am interested in the same question even for cubic polynomials in $\mathbb{Q}[x]$. Here is my formal question: https://math.stackexchange.com/questions/4192447/irreducibility-testing-for-integral-cubic-polynomials – Pranav Bisht Jul 07 '21 at 10:19

0 Answers0