5
$\begingroup$

This is a problem similar to one of my homework problems, but not on the homework. The problem states that:

Find a primitive root $\beta$ of $F_2[x]/(x^4+x^3+x^2+x+1)$.

Questions:

  1. I know what a primitive root of a prime number is, but what is a primitive root of a polynomial (or is it called something like a field extension here)?

  2. My book gives this hint: $[x]=\alpha$ doesn't work because $\alpha^5=1$. There are eight choices of $\beta$. I am basically lost on the hint. What is $\alpha$? Why doesn't it work? Why are there 8 choices for $\beta$? Wouldn't there be $2^4 =16$ choices? (or that's the number of polynomials in the field?)

Sorry for the long questions, since I am quite lost right now. Hopefully my questions make sense, and any help would be appreciated!

  • 0
    It's not "primitive root of a polynomial", it's "primitive root of a finite field."2011-05-03
  • 0
    I guess it means to find an element whose powers give all nonzero elements of the extension. (This is analogous to how a primitive root modulo $p$ is an element of $\mathbb{F}_p$ whose powers give all nonzero elements of the extension.)2011-05-03
  • 0
    thanks for the comments! I also changed the title from "polynomial" to "finite field" :)2011-05-04
  • 0
    Added the *finite-fields* tag2011-06-25

1 Answers 1

7

The multiplicative group of nonzero elements of a finite field is always cyclic. A "primitive root" of a finite field is a generator for the multiplicative group of nonzero elements.

Note that $x^4+x^3+x^2+x+1$ is irreducible over $\mathbb{F}_2$: it has no roots, and it is not the product of two irreducible quadratics (the quadratics are $x^2$, $x^2+1$, $x^2+x$, and $x^2+x+1$, and the only irreducible one is the latter; but $(x^2+x+1)^2 = x^4 + x^2 + 1$). So $\mathbb{F}_2[x]/(x^4+x^3+x^2+x+1$ is a field of degree $4$ over $\mathbb{F}_2$ (hence, of order $2^4 = 16$). So you are looking for an element in the field of $16$ elements whose multiplicative order is exactly $15$. The book is noting that even though this field equals $\mathbb{F}_2(\alpha)$ (where $\alpha$ is the class of $x$ in the quotient), $\alpha$ doesn't work because it is of order $5$. That is: while it is true that if $\beta$ is a primitive root for the field $GF(p^k)$, then $GF(p^k) = \mathbb{F}_p(\beta)$, the converse does not necessarily hold as this example shows.

  • 3
    Why $8$ choices for $\beta$? The reason is hidden in Arturo's answer; let me make it a little more explicit. The field has $16$ elements; its multiplicative group is everything but zero, so it has $15$ elements; this group is cyclic, so we're dealing with the cyclic group of $15$ elements, and we want a generator (synonym, in this context, for primitive element). Of the $15$ elements of a cyclic group of order $15$, how many are generators?2011-05-03
  • 0
    @Gerry $\phi(15)=8$? lol, I am guessing...2011-05-04
  • 0
    by 8 choices for $\beta$, do you mean 8 primitive roots or 8 elements that can potentially be primitive roots? thanks!2011-05-04
  • 0
    @mathcat, yes, $\phi(15)=8$. Now, does a cyclic group of order $15$ have $8$ generators, or does it have $8$ elements that can potentially be generators?2011-05-04