<s>[INST] How can I prove irreducibility of polynomial over a finite field? 
I want to prove what $x^{10} +x^3+1$ is irreducible over a field $\mathbb F_{2}$ and $x^5$ + $x^4 +x^3 + x^2 +x -1$ is reducible over $\mathbb F_{3}$.

As far as I know Eisenstein criteria won't help here.
I have heard about a criteria of irreducibility which sounds like 

"If $f(x)$ divides $x^{p^n-1}-1$ (where $n=\deg(f))$, $p$ is from $\mathbb F_{p}$ then $f(x)$ is irreducible." 

But I don't know how to show if $f(x)$ can be divided by this or not.
 [/INST] Neither polynomial has zeros in the respective prime field, so they do not have linear factors either.
Let's check the first polynomial $p(x)=x^{10}+x^3+1\in\Bbb{F}_2[x]$. The claim is that it is irreducible. A more efficient way of using the cited result is to observe that if $p(x)$ were a product of two or more irreducible factors at least one of those factors would have degree $\le5$. We eliminate these possibilities one-by-one. Testing for the presence of higher degree factors becomes progressively a little bit harder as the degree goes up, but the principle is always the same, and this result gives us a tool.
Could it have an irreducible quadratic factor? By the cited result all the irreducible quadratic polynomials are factors of $p_2(x):=x^{2^2-1}-1=x^3+1$. To eliminate the possibility of $p(x)$ having a quadratic factor it thus suffices to show that $\gcd(p(x),p_2(x))=1$. Because $p(x)-p_2(x)=x^{10}$ any common factor they have is also a factor of $x^{10}$, but the only irreducible factor of $x^{10}$ is $x$, so we have cleared this obstacle.
To eliminate the possibility of $p(x)$ having a cubic factor it similarly suffices to check that $\gcd(p(x),p_3(x))=1$, where $p_3(x)=x^{2^3-1}-1=x^7+1$. Here we see (the first step in calculating this gcd by Euclid's algorithm) that
$$
p(x)-x^3p_3(x)=1,
$$
so no common factors there either.
To eliminate the possibility of a quartic factor of $p(x)$, we need to calculate $\gcd(p(x),p_4(x))$ with $p_4(x)=x^{2^4-1}-1=x^{15}+1.$ Let's run Euclid:
$$
\begin{aligned}
p_4(x)-x^5p(x)&=x^8+x^5+1=: r_1(x)\\
p(x)-x^2r_1(x)&=x^7+x^3+x^2+1=:r_2(x).
\end{aligned}
$$
Here we could continue with Euclid, but we can also save a step or two by factoring the remainder whenever we can do so easily. Here
$$
r_2(x)=x^3(x^4+1)+(x^2+1)=x^3(x^2+1)^2+(x^2+1)=(x^2+1)(x^5+x^3+1).
$$
We know from earlier steps that $p(x)$ is not divisible by $(x+1)$. Because
$(x^2+1)=(x+1)^2$, we can discard that factor as a possibility, and continue Euclid with $\gcd(r_1(x), r_3(x))$ where $r_3(x)=x^5+x^3+1$.
We see that
$$
\begin{aligned}
r_1(x)-x^3r_3(x)&=x^6+x^5+x^3+1=(x+1)(x^5+x^2+x+1)\\
&=(x+1)^2(x^4+x^3+x^2+1)=(x+1)^3(x^3+x+1).
\end{aligned}
$$
Here I used extensively the trick (based on geometric sums) that whenever $0<a<b$ we have
$$
\frac{x^a+x^b}{x+1}=x^a+x^{a+1}+x^{a+2}+\cdots+x^{b-1}.
$$
Anyway, the above calculation shows that any eventual common factor of $p(x)$ and $p_4(x)$ is also a factor of the cubic $x^3+x+1$, but we already showed that $p(x)$ has no cubic factors. Therefore we are done with this case, too.
The last step of proving that $p(x)$ as no quintic factors needs another run of Euclid. This time checking that $\gcd(p(x),p_5(x))=1$, where $p_5(x)=x^{31}+1$. To get started we use square-and-multiply. We already calculated in the previous step that
$$
x^{15}\equiv x^8+x^5\pmod{p(x)}.\qquad(*)
$$
Consequently $x^{16}\equiv x^9+x^6\pmod{p(x)}$. Squaring $(*)$ (Freshman's dream simplifies squaring in characteristic two) gives
$$
x^{30}\equiv x^{16}+x^{10}\equiv (x^9+x^6)+x^{10}\pmod{p(x)}.
$$
Here
$$
x^{10}+x^9+x^6-p(x)=x^9+x^6+x^3+1.
$$
Therefore (multiply by $x$)
$$
x^{31}\equiv x^{10}+x^7+x^4+x\equiv x^7+x^4+x^3+x+1\pmod{p(x)}.
$$
So we know the remainder of $p_5(x)$ modulo $p(x)$. The remaining task is thus to check that
$$
\gcd(p(x),x^7+x^4+x^3+x)=1.
$$
Leaving that to you :-)
Your other polynomial
$$
q(x)=x^5+x^4+x^3+x^2+x-1\in\Bbb{F}_3(x)
$$
is quintic. So if it is reducible, it must have one factor that is either linear or a quadratic. We eliminated the possibility of linear factors by checking that it has no zeros. Using the above technique we find eventual quadratic factors by calculating
$$
\gcd(q(x),q_2(x))\in\Bbb{F}_3[x].
$$
Here $q_2(x)=x^{3^2-1}-1=x^8-1$. Leaving it to you to run this instance of Euclid, and find the quadratic factor.
</s>