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

<p>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.</p>

CC BY-SA 3.0
2013-06-29T01:19:05.340Z
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
CC BY-SA 3.0
2013-06-29T07:26:08.617Z
@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
CC BY-SA 3.0
2013-06-29T14:40:17.947Z
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
CC BY-SA 3.0
2013-06-29T14:45:23.697Z
@Bruno, if the polynomial is primitive, I believe LLL takes cares of factoring in poly time. Am I correct?
Turbo
CC BY-SA 3.0
2013-06-29T15:18:43.533Z
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
CC BY-SA 3.0
2013-06-29T15:29:39.800Z
I want to avoid LLL since I am only looking for a test for reducibility.
Turbo
CC BY-SA 3.0
2015-03-30T16:49:19.927Z
(afaik) isnt this closely connected to [polynomial identity testing](http://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma)? 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](http://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm) algorithm
vzn
CC BY-SA 3.0
2015-03-30T19:38:49.383Z
@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
CC BY-SA 3.0
2015-03-30T20:35:24.577Z
the general idea is a connection between factoring and [testing equivalence](http://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma#Comparison_of_two_polynomials) 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](http://eccc.hpi-web.de/report/2014/001/) Kopparty, Saraf, Shpilka
vzn
CC BY-SA 3.0
2015-03-30T23:56:06.373Z
@vzn I apologize it is still unclear to me what exactly connection is.
Turbo
CC BY-SA 4.0
2021-04-10T02:26:56.933Z
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
CC BY-SA 4.0
2021-04-10T02:40:23.207Z
(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
CC BY-SA 4.0
2021-07-07T10:16:57.397Z
@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
CC BY-SA 4.0
2021-07-07T10:19:23.150Z
@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
<open-problem><algebraic-complexity>
Identifying Reducible/Irreducible polynomials over $Z[x]$
Turbo
# Identifying Reducible/Irreducible polynomials over $Z[x]$

(Asked by: username_0 on 2013-06-28)

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.

**Tags:** open-problem, algebraic-complexity

> **Comments:**
> **username_1**: 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$.  
> **username_0**: @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?  
> **username_2**: 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.  
> **username_0**: @username_2, if the polynomial is primitive, I believe LLL takes cares of factoring in poly time. Am I correct?  
> **username_2**: 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!  
> **username_0**: I want to avoid LLL since I am only looking for a test for reducibility.  
> **username_3**: (afaik) isnt this closely connected to [polynomial identity testing](http://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma)? 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](http://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm) algorithm  
> **username_0**: @username_3 How is deciding $f(x)\in\Bbb Z[x]$ splits in $\Bbb Z[x]$ related to PIT? Problem seems simpler than actual splitting.  
> **username_3**: the general idea is a connection between factoring and [testing equivalence](http://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma#Comparison_of_two_polynomials) 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](http://eccc.hpi-web.de/report/2014/001/) Kopparty, Saraf, Shpilka  
> **username_0**: @username_3 I apologize it is still unclear to me what exactly connection is.  
> **username_4**: 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 username_3'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.  
> **username_4**: (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.)  
> **username_5**: @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.  
> **username_5**: @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  

---

## 0 answers

