Irreducible Polynomial in $\mathbb F_{256}$. Let $\mathbb F_{256}$ be the finite field with $2^8 = 256$ elements. Consider the polynomial over this field
$$
  x^2 + x + 1.
$$
I wanted to know if it is irreducible, so I calculated it for all values $0, \ldots, 256$ and considered the remainder modulo 256, I found that it doesn't evaluates to $0$, so I guess it is irreducible, but is this a valid method?
 A: The method you cite should work, because the polynomial is of degree $2$ and hence any factors will correspond to solutions of the equation $x^2+x+1=0$. But you have to do it right and work over the field $\mathbb F_{256}$, which means you must begin by constructing that field etc. Working over the integers modulo 256 (i.e. $\mathbb Z/256\mathbb Z$) will not do.
Here is my suggestion to avoid this work: the polynomial is irreducible over $\mathbb F_2$ but it becomes reducible over $\mathbb F_4$ and extensions thereof. Since $256 = 2^8$ and $8$ is even, it contains $\mathbb F_4$ as a subfield and hence the polynomial is reducible.
A: As "Myself" observed, you are apparently misconstruing $\mathbb F_{2^8}$ as being isomorphic to $\mathbb Z/2^8$, which it is not. For example, the latter has many zero-divisors, and is far from being a field.
Also, in any case, for human-executable work checking 256 cases is usually a terrible method. Instead, look for some structure or meaning. Here, the polynomial $x^2+x+1$ is the third cyclotomic polynomial $(x^3-1)/(x-1)$, and has the property that a root of it (in any field) has multiplicative order $3$. Thus, if there is a root, by Lagrange's theorem $3$ divides the order of the multiplicative group. Conversely, by Cauchy's theorem, if $3$ divides that order then the equation has a root. Thus, it has a root in the field with $2^8$ elements if and only if the multiplicative group has order divisible by $3$. Since $2^8-1=255=5\cdot 51=5\cdot 3\cdot 17$, there is a factor of $3$, and the polynomial has a root, and is reducible.
A: The polynomial you write is the third cyclotomic polynomial. It is reducible in any finite field $\Bbb F_q$ where $3$ divides the order $q-1$ of the multiplicative group. In the case $q=256$ we find that $3$ divides $255$, so the polynomial splits in $\Bbb F_{256}[x]$.
A: First: looking for roots to deduce a polynomial over some field is irreducilbe works as long as the polynomials degree $\,\le 3\,$ .
Second: the polynomial $\,x^2+x+1\,$ is defined over $\,\Bbb F_2\,$ and it's irreducible over this field. Since $\,2\mid 8\;$, we have that $\,\Bbb F_{2^2}\le\Bbb F_{2^8}\,$ , and this means that all the roots of $\,x^2+x+1\,$ are already in $\,\Bbb F_{2^8}\,$ so either you didn't check correctly or else, as a comment above hints, you confused $\,\Bbb F_{256}\,$ with $\,\Bbb Z_{256}\,$ .
