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!

-
Caw, the notation and terminology in 2) is (at least to me) non-standard. What does the $n$ in $\mathbb{F}_2^n$ mean? Do you really mean polynomials over the product ring $\mathbb{F}_2^n$? Or, perhaps do you mean $\mathbb{F}_{2^n}$? Also, what is a "primitive root"? If you mean a primitive element, then the definition of this is precisely that it generates a power-basis for your extension. – Alex Youcis Mar 30 '13 at 5:58
@AlexYoucis: In the context of finite fields primitive elements are the generators of the (cyclic) multiplicative group. This is a stronger requirement than elsewhere in field theory, where giving a monomial basis is enough. – Jyrki Lahtonen Mar 30 '13 at 6:07
@JyrkiLahtonen Ah, ok. I'm certainly aware of the terminology in the case $\mathbb{Z}/p\mathbb{Z}$--I was unaware that it was used in the contexts of other fields. Does the $\mathbb{F}_2^n$ make sense to you? – Alex Youcis Mar 30 '13 at 6:09
@Alex: No :-) I guess it would be a typo and $\mathbb{F}_{2^n}$ was intended (a synonym for $GF(2^n)$). – Jyrki Lahtonen Mar 30 '13 at 6:30
No, that doesn't make sense either. Has to be just $\mathbb{F}_2[x]/(x^8+x^4+x^3+x+1)$. – Jyrki Lahtonen Mar 30 '13 at 6:31

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.

-
This is exactly what I was asking, thank you! – caw Mar 30 '13 at 21:06

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.

-
Ah, I should have said "an irreducible polynomial" of degree eight. – Erno Lancaster Apr 2 '13 at 6:51