Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
1  
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
show 2 more comments

2 Answers

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.

share|improve this answer
    
This is exactly what I was asking, thank you! –  caw Mar 30 '13 at 21:06
add comment

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.

share|improve this answer
    
Ah, I should have said "an irreducible polynomial" of degree eight. –  Erno Lancaster Apr 2 '13 at 6:51
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.