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

• 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}$.
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.