Can irreducibility of polynomials be figured out in polynomial time? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T03:28:25Z http://mathoverflow.net/feeds/question/73031 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/73031/can-irreducibility-of-polynomials-be-figured-out-in-polynomial-time Can irreducibility of polynomials be figured out in polynomial time? Yuhao Huang 2011-08-17T04:47:05Z 2011-08-17T11:51:45Z <p>I remember seeing somewhere "primarity test (of numbers) is harder than irreducibility test (of polynomials)", now as primarity test in polynomial time is known, can irreducibility test of polynomials over the integers be done in a fast way?</p> <p>(I'm not sure if this is a well-defined question, as both the degree and coefficients can be large, maybe let me ask, can the primarity test of f(x) be done in $\text{O}(N^i(\log N)^j)$ operations, where N is f(m), with m = sum of absolute value of coefficients?)</p> http://mathoverflow.net/questions/73031/can-irreducibility-of-polynomials-be-figured-out-in-polynomial-time/73037#73037 Answer by Gerry Myerson for Can irreducibility of polynomials be figured out in polynomial time? Gerry Myerson 2011-08-17T06:58:49Z 2011-08-17T06:58:49Z <p>You might be interested in Adleman and Odlyzko, Irreducibility testing and factorization of polynomials, Math Comp 41 (1983) 699-709. The abstract says, "It is shown that under certain hypotheses, irreducibility testing and factorization of polynomials with integer coefficients are polynomial time reducible to primality testing and factorization of integers, respectively." </p> http://mathoverflow.net/questions/73031/can-irreducibility-of-polynomials-be-figured-out-in-polynomial-time/73039#73039 Answer by Bruno for Can irreducibility of polynomials be figured out in polynomial time? Bruno 2011-08-17T07:15:47Z 2011-08-17T07:15:47Z <p>As you correctly states it, your question is not completely well-defined. Actually, two quite different problems have been studied a lot: factorization of <em>dense</em> polynomials and of <em>sparse</em> polynomials. These two problems differ by the input they receive. This is especially relevant for univariate polynomials. </p> <ul> <li><strong>Factorization of dense polynomials</strong> is the problem of given a sequence $[a_0,\dotsc,a_n]$, factorize $P(X)=\sum_{i=0}^n a_i X^i$. </li> <li><strong>Factorization of sparse polynomials</strong> is the problem of given a sequence of couples $[(a_0,d_0),(a_1,d_1),\dotsc,(a_n,d_n)]$, factorize $P(X)=\sum_{i=0}^n a_i X^{d_i}$.</li> </ul> <p>Clearly, in the sparse version, your polynomials can have large degrees (exponential in the size of the input) while in the dense version, the degree is bounded by the size of the input. This is why the dense case is pretty well understood (for univariate as well as for multivariate polynomials) whence in the sparse case only some partial results are known. </p> <p>A good way to know what has been done on the subject is to have a look to <a href="http://www4.ncsu.edu/~kaltofen/bibliography/kaltofen.html#SECTION00021000000000000000" rel="nofollow">Erich Kaltofen's publications on this subject</a>. You'll find his results and of course the relevant literature in the references. He also has several surveys on polynomial factorization, you can in particular have a look to <a href="http://www.math.ncsu.edu/~kaltofen/bibliography/03/Ka03.pdf" rel="nofollow">the most recent one</a> (2003). </p> http://mathoverflow.net/questions/73031/can-irreducibility-of-polynomials-be-figured-out-in-polynomial-time/73050#73050 Answer by Steve Huntsman for Can irreducibility of polynomials be figured out in polynomial time? Steve Huntsman 2011-08-17T11:43:11Z 2011-08-17T11:51:45Z <p>Polynomial factorization (hence also irreducibility testing) over $\mathbb{F}_q[x]$ can be done eﬃciently using the <a href="http://en.wikipedia.org/wiki/Berlekamp%27s_algorithm" rel="nofollow">Berlekamp</a> or similar algorithms (for polynomial rings over other fields the situation is different). See, e.g., <a href="http://www.johnkerl.org/doc/iw2009/berlekamp.pdf" rel="nofollow">this PDF</a> for an elementary discussion.</p>