A question about irreducible polynomials, roots, and polynomial bases I have a couple questions about the mathematical jargon that's thrown around in the literature all too often. To my knowledge, an irreducible polynomial is one that cannot be factored, meaning that it has no roots. However, several papers (see Section 2 in the link below) like to say that it is possible for an irreducible polynomial to have a root, and furthermore, for that root $\alpha$ to be used in the polynomial basis of a field $GF(2^n)$ as $[\alpha^n-1,\dots,\alpha,1]$. 
http://teal.gmu.edu/courses/ECE746/project/S08_Project_resources/Canright_CHES.pdf
My questions are as follows:
1) As claimed in the referenced paper, how can an irreducible (not primitive) polynomial have a root? 
2) If I have a generator (primitive root) of a field $\mathbb{F}_{2}[x]/(x^8 + x^4 + x^3 + x + 1)$, say $\alpha = x + 1$, does that mean $[\alpha^7,\dots,\alpha^2,\alpha,1]$ is a valid polynomial basis? 
Thanks in advance for the help!
 A: To give an example for your first question: no matter what field you're working over, the polynomial $x$ is irreducible, and obviously has a root, namely $0$.
In general, a polynomial will always have roots, though maybe not over the field which you started with. For example, $x^2+1$ has no roots in $\mathbb{R}$, and it also happens to be irreducible as an element of the ring $\mathbb{R}[x]$, but we know that it does have roots: namely, $i$ and $-i$, which live in $\mathbb{C}$. This leads to the concept of the splitting field of a polynomial.
Given a field $K$, and a polynomial $f\in K[x]$, $f$ being irreducible does not mean "$f$ has no roots in $K$". Irreducible means that, for any polynomials $g$ and $h$ such that $f=gh$, either $g$ or $h$ is a non-zero constant (but not both). This is just an instance of the general definition of irreducible element; in other words, an irreducible polynomial is just an irreducible element of a polynomial ring.
Moreover, there are polynomials that are reducible but still have no roots in the given field. A classic example is $x^4+4$, considered as an element of $\mathbb{Q}[x]$, which has no roots in $\mathbb{Q}$ but factors as
$$x^4+4=(x^2+2x+2)(x^2-2x+2).$$

To answer your second question (if I've interpreted it correctly): if we start with $\mathbb{F}_2$ and take a generating element $\alpha\in \mathbb{F}_{2^r}$ (that is, one for which $\alpha,\alpha^2,\ldots,a^{2^r-1}$ runs through all $2^r-1$ non-zero elements of $\mathbb{F}_{2^r}$), then we must have $\mathbb{F}_{2^r}=\mathbb{F}_2(\alpha)$, so we see that $\{1,\alpha,\ldots,\alpha^r\}$ is a basis for $\mathbb{F}_{2^r}$, considered as an $\mathbb{F}_2$-vector space.
A: When you say a polynomial is irreducible or has roots, you must qualify that statement with an appropriate finite field. The finite field you talk about may not always be immediately obvious.
For example, $x^8+x^4+x^3+x+1$ is irreducible in $\mathrm{GF}(2)$. However, it is not irreducible in $\mathrm{GF}(2^8)$. A polynomial An irreducible polynomial of degree $d$ in a finite field of size $q$ will always have roots in an extended field of size $q^d$ (In fact, this is the smallest such field). So, you use the properties of one such arbitrary root to define the extended field.
