Since $f(X)$ is monic, it is irreducible over $\Bbb{Z}$ iff it is irreducible over $\Bbb{Q}$. But Eisenstein Criterion is not applicable here. I was trying to reduce it to mod $p$ for some prime $p$ and check whether it is irreducible over $\Bbb{Z}/p\Bbb{Z}$. I was trying to shift and then apply Eisenstein but none of them seems working.
Can anyone give me any hint or wayout to solve the problem? Thanks for your help in advance.
On
This is is more a remark than an answer, but I thought you might be interested. It would take an impractically long time, but in principle there is a straightforward algorithm to decide whether any integer polynomial is irreducible.
Here's the idea. Suppose, for instance, that it is possible to write $f(X)=g(X)h(X)$ where $g$ has degree $3$ and $h$ has degree $4$. Now, for any integer $n$, there are only finitely possibilities for the values of $g(n)$ and $h(n)$ because there are only finitely ways to factor $f(n)$ as a product of two integers. On the other hand, to determine $g$ and $h$ uniquely, we only need $3$ evaluations of $g$ and $4$ evaluations of $h$.
So, all we need to do is look at $4$ values of $f$ and all the ways those values can be factored. We can use any $4$ values of $f$, but ideally we choose values with fewer factors. Let's look at:
\begin{align*} f(0)&=9 \leftarrow \text{two prime factors} &&& f(1)&=21 \leftarrow\text{two prime factors} \\f(-1)&=7 \leftarrow \text{prime}&&& f(2)&=349 \leftarrow \text{prime} \end{align*}
Now, we can consider one of the finitely many ways of factoring those numbers. Note the order of multiplication matters here as we associate the left factor with $g$ and the right factor with $h$. \begin{align*} 9=3 \cdot 3 && 21 = 3 \cdot 7 && 7 = 1 \cdot 7 && 349 =349 \cdot 1 && (**) \end{align*} Now we ask:
We come up with \begin{align*} g(X)=-X^2+X+3 && h(X)=-3X^3+4X^2+3X+3.\end{align*} However, the product of these is $$3X^5 - 7X^4 - 8X^3 + 12X^2 + 12X + 9 \neq f(X).$$ so the choices $(**)$ did not lead us to a factorization.
Continuing in this way, you can eventually establish for certain whether it is possible to factor $f(X)$ as the product of a degree $3$ and a degree $4$ polynomial. Then, in a similar way, you can check whether it is possible to factor $f(X)$ as the product of a degree $2$ and a degree $5$ polynomial.
Obviously, it would take a very long time to carry out all these steps, but you might find it comforting to know that there is a deterministic procedure. There are also ways of doing this more efficiently which you can find out about by searching for "Newton polygon".
On
Over $\mathbb{F}_2$, $f$ factors as $$(x^2 + x + 1) * (x^5 + x^4 + x^2 + x + 1), $$ a degree $2$ times a degree $5$. Over $\mathbb{F}_{11}$, $f$ factors as $$(x + 6) * (x^6 + 5*x^5 + 9*x^4 + x^3 + 5*x^2 + 8*x + 7).$$ This is a degree $1$ and a degree $6$. These are incompatible factorizations --- a factorization over $\mathbb{Z}$ descends to factorizations over any $\mathbb{F}_p$. Thus $f$ is irreducible.
Edit: a computational shortcut
Determining reducibility/irreducibility over finite fields is a finite, but possibly tedious, process. Thus one way to factor $f$ over $\mathbb{F}_{11}$ is to check for roots (giving the linear factor), and then check for quadratic factors, and then check for cubic factors. The degree $6$ part will either be irreducible or have a degree $1$, $2$, or $3$ factor.
But there is a slightly faster computational way to determine that $f$ is irreducible over $\mathbb{Z}$. The factorization over $\mathbb{F}_2$ gives a degree $2$ term and a degree $5$ term. Over $\mathbb{F}_{11}$, we identify the linear term quickly by looking for roots (by plugging in $11$ numbers). It is quick to verify that this is a single root and that $f$ has no other roots over $\mathbb{F}_{11}$.
Thus there is exactly one linear factor. To check compatible factorizations with the factorization over $\mathbb{F}_2$, it now suffices to check for an irreducible quadratic factor. Confirming that such a factor doesn't exist completes the demonstration that $f$ is irreducible. Note that it isn't necessary to look for cubic factors, or to completely verify that the sextic in the factorization is irreducible.
The polynomial is indeed irreducible over $\Bbb F_{29}$, hence also irreducible over $\Bbb Z$. Of course one still needs some work to show this for $p=29$. A short computation shows that $f$ has no root in $\Bbb F_{29}$, so that we have to look at the cases $f=(x^2+ax+b)(x^5+\cdots +a_0)$ and $f=(x^3+ax^2+bx+c)(x^4+\cdots +b_0)$.