# Can irreducibility of polynomials be figured out in polynomial time?

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?

(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?)

-

As you correctly states it, your question is not completely well-defined. Actually, two quite different problems have been studied a lot: factorization of dense polynomials and of sparse polynomials. These two problems differ by the input they receive. This is especially relevant for univariate polynomials.

• Factorization of dense polynomials is the problem of given a sequence $[a_0,\dotsc,a_n]$, factorize $P(X)=\sum_{i=0}^n a_i X^i$.
• Factorization of sparse polynomials 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}$.

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.

A good way to know what has been done on the subject is to have a look to Erich Kaltofen's publications on this subject. 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 the most recent one (2003).

-

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."

-

Polynomial factorization (hence also irreducibility testing) over $\mathbb{F}_q[x]$ can be done eﬃciently using the Berlekamp or similar algorithms (for polynomial rings over other fields the situation is different). See, e.g., this PDF for an elementary discussion.

-