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!
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.