I have learnt a theorem that there always exists an irreducible polynomial of an arbitrary degree $m$ over a finite field. This theorem, of course, ensures the existence of an irreducible polynomial
of degree $p$, but how to actually find such a polynomial? Any help would be appreciated!
Find an irreducible polynomial of degree $p$ over finite field $F_p$ where $p$ is prime
field-theoryfinite-fields
Best Answer
An irreducible polynomial $f(x)$ of degree $n$ over $\mathbb{F}_p$ is necessarily a divisor of $x^{p^n}-x$.
Which gives a known criterion: $f(x)\in\mathbb{F}_p[x]$ is irreducible if and only if $f(x)\mid x^{p^n}-x$, where $n=\deg f$, and for each prime $d\mid n$ we have $\gcd\big(f(x),x^{p^{n/d}}-x\big)=1$. In terms of roots of $f$ (in an algebraic closure of $\mathbb{F}_p$), these must be distinct (this is checked by $\gcd(f,f')=1$), and any root $\alpha$ must satisfy $\alpha^{p^n}=\alpha$ but $\alpha^{p^{n/d}}\neq\alpha$ for each prime $d\mid n$.
This gives an easy way to check that $g(x):=x^p-x-1\in\mathbb{F}_p[x]$ is irreducible. Since $g'=-1$, the condition $\gcd(g,g')=1$ holds trivially. Let $\alpha$ be a root of $g(x)$. Then, by induction, $\alpha^{p^k}=\alpha+k$ for any natural $k$, hence $\alpha^{p^p}=\alpha$. Since $d=p$ is the only possibility here, and $\alpha^{p^1}=\alpha+1\neq\alpha$, we're done.