Suppose you have a polynomial with degree large enough that just checking factors of various degrees is inefficient. Suppose additionally that Eisenstein's criterion fails for all possible shifts of the polynomial. What other methods are there for testing for the irreducibility?
For example I know that $x^{11} + x + 3$ is irreducible over $\mathbb Q$, but how could I prove this?
In the case of $x^{11} + x + 3$, it suffices to prove (or check) that all its complex roots $z_1,\ldots, z_{11}$ have absolute values that are $> 1$. Indeed if $z$ is a root, $3=|z^{11}+z|\leq |z|^{11}+|z|$, hence $|z|$ is larger than the real root of $x^{11}+x-3$, which can be approximated by usual methods as $1.062$.
Remember that irreducibility over $\mathbb Q$ is equivalent to irreducibility over $\mathbb Z$. Then, if the polynomial splits as $PQ$ where $P,Q\in \mathbb Z[X]$ and $\deg P = k \geq 1$, we may assume WLOG that the constant coefficient of $P$ is $\pm 3$ and that the complex roots of $P$ are $z_1,\ldots z_k$ thus $$|z_1\ldots z_k|=3 = |z_1\ldots z_{11}|$$ hence $|z_{k+1}\ldots z_{11}|=1$, a contradiction.