Represent all elements of a field in terms of a primitive element

a)Taking a primitive element $u$ of $\mathbb{F}_8$, compute the table listing elements of $\mathbb{F}_8$ in two representations, as powers of $u$ and as linear combinations of the basis {$1,u,u^2$} over $\mathbb{Z}_2$
b)Compute all roots of the irreducible polynomial for $u$ in $\mathbb{F}_8$

Since $\mathbb{F}_8$ is isomorphic to $\mathbb{Z}_8$ can I just consider $\mathbb{Z}_8$? If this is the case then I can represent each elements as a power of 3 as shown below, but I'm not sure how to represent each element as a linear combination of basis elements. From other problems I've done in this chapter, I'm guessing that it has something to do with picking a monic irreducible polynomial and then just substituting in for powers of $u$ that are higher than 2, but I could be way off base. I'm also not sure how to approach b. I know that if $a$ is a primitive element of a field of size $q$ then for any nonzero element $b \in F$ there exists a $t$ such that $a^t = b$, but not quite sure how to use that

• Why do you think $\Bbb F_8 \cong \Bbb Z_8$? – Robert Lewis Apr 17 '18 at 4:49
• Well I know for a prime number $p$ we have $\mathbb{F}_p \cong \mathbb{Z}_p$. I thought it was also for powers of primes. I'm guessing its not? – Vinny Chase Apr 17 '18 at 4:51
• @RobertLewis Now I'm even more confused because I'm trying to fill in this table and by the last line that I wrote we know that there exists a $t$ such that $b=u^t$, but I see nothing in my notes that says how to find said $t$ – Vinny Chase Apr 17 '18 at 4:57
• @RobertLewis That makes sense. Do you have any hints on how to proceed? The only things in my notes about primitive elements are the definition, that the number of them equals the result of the Euler Phi function and what I wrote in my last comment so I'm pretty stuck – Vinny Chase Apr 17 '18 at 5:01
• Let me see, I guess I would start with the fact that $\vert \Bbb F_{2^3}^\times \vert =7$, so it is cyclic of prime order, so any non-unit element is a generator. Also, I'm guessing that a primitive element of $\Bbb F_{2^3}$ satisfies $x^3 + x + 1 \in F_2[x]$ which is irreducible. Then you need to use the polynomial, e.g. if $u$ is primitive we have $1, u, u^2, u^3 = u + 1, u^4 = uu^3 = u^2 + u, \ldots$. This gives all powers of $u$ as linear combinations in $1, u, u^2$. Cheers! – Robert Lewis Apr 17 '18 at 5:15

1 Answer

Pretty long winded, this one, but I tried to cover all the bases (the ones I could see at least) from more-or-less first principles.

OK, let's start by finding the irreducible cubics over $\Bbb F_2$, the ones in $\Bbb F_2[x]$. We note that each must be of the form

$\alpha x^3 + \beta x^2 + \gamma x + \delta \in \Bbb F_2[x], \tag 1$

that is,

$\alpha, \beta, \gamma, \delta \in \Bbb F_2; \tag 2$

we must have

$\alpha = 1 \tag 3$

to make sure the polynomials are of degree three, and then we must have $\delta = 1$ to make sure the polynomials are irreducible; otherwise,

$x^3 + \beta x^2 + \gamma x = (x^2 + \beta x + \gamma)x, \tag 4$

and the polynomial can be factored. So we are left with elements of $\Bbb F_2[x]$ of the form

$x^3 + \beta x^2 + \gamma x + 1; \tag 5$

now we must have

$\beta \ne \gamma; \tag 6$

otherwise, $1$ is a zero of (5). So now there are only two possible cases,

$\beta = 1, \; \gamma = 0, \tag 7$

yielding

$x^3 + x^2 + 1, \tag 8$

and

$\beta = 0, \; \gamma = 1, \tag 9$

which gives

$x^3 + x + 1. \tag{10}$

Since neither (8) nor (10) have a zero in $\Bbb F_2$, they must both be irreducible; being of degree three, a linear factor would appear in any factorization, which would correspond to a root; but that possibility has been ruled out. Thus, both (8) and (10) are irreducible cubic polynomials over $\Bbb F_2$, and there are no others.

Now let

$u \in \Bbb F_{2^3} \setminus \Bbb F_2; \tag{11}$

that is, $u \in \Bbb F_{2^3}$ but $u \ne 0, 1$; in this event, we have that the set $\{1, u, u^2 \}$ is linearly independent over $\Bbb F_2$; for if not, there exist $\alpha, \beta, \gamma \in \Bbb F_2$, not all zero, with

$\alpha u^2 + \beta u + \gamma = 0; \tag{13}$

$\alpha \ne 0$ in (13) lest it reduce to

$\beta u + \gamma = 0; \tag{14}$

we rule out the case $\beta \ne 0$ in (14) because it leads to

$u = -\dfrac{\gamma}{\beta} \in \Bbb F_2, \tag{15}$

and if $\beta = 0$ then (14) reduces to

$\gamma = 0; \tag{16}$

but then we have $\alpha = \beta = \gamma = 0$, contrary to our assumption that not all these coefficients vanish. Thus we are forced to assume $\alpha \ne 0$ in (13); then $\alpha = 1$ and we have

$u^2 + \beta u + \gamma = 0; \tag{17}$

now we must have $\gamma \ne 0$ lest

$u(u + \beta) = u^2 + \beta u = 0, \tag{18}$

which forces $u \in \Bbb F_2$, a in contradiction to (11) (if $u \ne 0$ (18) forces $u = \beta \in \Bbb F_2$); thus (17) beomes

$u^2 + \beta u + 1 = 0; \tag{18}$

if $\beta = 0$ then

$(u + 1)^2 = u^2 + 2u + 1 = u^2 + 1 = 0, \tag{19}$

forcing

$(u + 1) = 0 \tag{20}$

or

$u = 1 \in \Bbb F_2; \tag{21}$

after all this ((11)-(21)) we see that the set $\{1, u, u^2 \}$ is linearly dependent over $\Bbb F_2$ only if

$u^2 + u + 1 = 0, \tag{22}$

or

$u^2 = u + 1, \tag{23}$

whence

$u^3 = u^2 + u = 1, \tag{24}$

which in turn implies that the set $\{1, u, u^2 \}$ takes on the structure of the unique (up to isomorphism) cyclic group with $3$ elements which is clearly a subgroup of $F_8^\times = F_{2^3}^\times$, the multiplicative group of non-zero elements of the field $\Bbb F_{2^3}$; but $\vert \Bbb F_{2^3}^\times \vert = 7$, so by Lagrange's theorem it cannot have a subgroup of order $3$, $3 \not \mid 7$; therefore, at last we see that the set $\{1, u, u^2 \}$ is linearly independent over $\Bbb F_2$. From here it is easy to see that

$\{\alpha + \beta u + \gamma u^2 \mid \alpha, \beta, \gamma \in \Bbb F_2 \} = \Bbb F_{2^3}, \tag{25}$

since the sets on either side have eight elements.

We recall in passing that (11) is essentially a statement that $u$ is primitive in $\Bbb F_{2^3}$; since $\vert \Bbb F_{2^3}^\times \vert = 7$, $\Bbb F_{2^3}^\times$ is cyclic of prime order and as such is generated by any of its own non-identity elements. We have this proven that $\{1, u, u^2\}$ is a basis for any primitive element of $\Bbb F_{2^3}$.

Now since $\{1, u, u^2 \}$ forms a basis for $\Bbb F_{2^3}$ over $\Bbb F_2$, any element of $\Bbb F_{2^3}$ is expressible as a linear combination of $1, u, u^2$; in particular we have

$u^3 = \alpha u^2 + \beta u + \gamma, \; \alpha, \beta, \gamma \in \Bbb F_2, \tag{26}$

which, since we are working in characteristic $2$, may be written

$u^3 + \alpha u^2 + \beta u + \gamma = 0, \; \alpha, \beta, \gamma \in \Bbb F_2; \tag{27}$

now the polynomial

$\chi(x) = x^3 + \alpha x^2 + \beta x + \gamma \in F_2[x] \tag{28}$

which $u$ satisfies must in fact be irreducible over $\Bbb F_2$; if not, we could write

$\chi(x) = (x + \theta)(x^2 + \mu x + \nu), \; \theta, \mu, \nu \in \Bbb F_2; \tag{29}$

since $\chi(u) = 0$ we would have

$(u + \theta)(u^2 + \mu u + \nu) = 0, \tag{30}$

which, since $u \notin \Bbb F_2$ enforces $u + \theta \ne 0$ and thus further forces

$u^2 + \mu u + \nu = 0, \tag{31}$

in contradiction to the proven fact that $\{1, u, u^2 \}$ is a linearly independent set over $\Bbb F_2$; thus $\chi(x)$ is irreducible and hence is of one of the two forms (8), (10) discovered in the first paragraph. At this point we observe that, substituting $x + 1$ for $x$ in (8) we find

$(x + 1)^3 + (x + 1)^2 + 1$$= x^3 + x^2 + x + 1 + x^2 + 1 + 1 = x^3 + x + 1, \tag{32}$

and likewise with repsect to (10),

$(x + 1)^3 + (x + 1) + 1$ $x^3 + x^2 + x + 1 + x + 1 + 1 = x^3 + x^2 + 1, \tag{33}$

which shows that the 2 polynomials (8), (10) map one to the other under the transformation $x \to x + 1$, and we further note that $\{1, u, u^2 \}$ forms a basis if and only if $\{1, u + 1, u^2 + 1 = (u + 1)^2 \}$ does. The upshot of these observstions is that, while we have no way of knowing a priori which irreducible polynomial (8) or (10) an arbitrary primitive $u$ obeys, we may rest assured it satisfies one of the two, and that $u + 1$ will be a root of the other.

It is now a relatively simple matter to work out the linear combinations of the basis $\{1, u, u^2 \}$ corresponding to given powers of $u$, once we have accepted which irreducible has $u$ as a root. For example, suppose $u$ satisfies (8), that is

$u^3 + u^2 + 1 = 0; \tag{34}$

then we have

$1 = 1; \tag {35}$

$u = u; \tag{36}$

$u^2 = u^2; \tag{37}$

$u^3 = u^2 + 1; \tag{38}$

$u^4 = uu^3 = u^3 + u = u^2 + u + 1; \tag{39}$

$u^5 = uu^4 = u^3 + u^2 + u = u^2 + 1 + u^2 + u = u + 1; \tag{40}$

$u^6 = uu^5 = u^2 + u; \tag{41}$

finally,

$u^7 = u^3 + u^2 = 1. \tag{42}$

Now turning to part (b) of the question, we see that we may easily calculate, via (35)-(42), which elements of $\Bbb F_8 = \Bbb F_{2^3}$ satisfy the irreducible cubic

$\chi(x) = x^3 + x^2 + 1 \tag{43}$

obeyed by $u$. We simply scan through the list and evalutat $\chi(u)$ for each entry:

$\chi(1) = 1^3 + 1^2 + 1 = 1; \tag{44}$

obviously,

$\chi(u) = 0; \tag{45}$

$\chi(u^2) = (u^2)^3 + (u^2)^2 + 1 = u^6 + u^4 + 1 = u^2 + u + u^2 + u + 1 + 1 = 0; \tag{46}$

$\chi(u^3) = u^9 + u^6 + 1 = u^7u^2 + u^6 + 1 = u^2 + u^2 + u + 1 = u + 1; \tag{47}$

$\chi(u^4) = u^{12} + u^8 + 1 = u^7u^5 + u^7u + 1 = u^5 + u + 1 = u + 1 + u + 1 = 0; \tag{48}$

$\chi(u^5) = u^{15} + u^{10} + 1 = (u^7)^2 u + u^7u^3 + 1$ $= u + u^3 + 1 = u + u^2 + 1 + 1 = u^2 + u; \tag{49}$

$\chi(u^6) = u^{18} + u^{12} + 1 = (u^7)^2 u^4 + u^7u^5 + 1$ $= u^4 + u^5 + 1 = u^2 + u + 1 + u + 1 + 1 = u^2 + 1; \tag{50}$

Note: I'm posting this as is, even though I have a few more words on the subject (just to make sure this post is long enough!), at the behest of my colleague Vinny Chase who has been patiently waiting for my answer for a couple of days. Haven't thoroughly checked this yet; hope it is error-free. End of Note.

• Over any field, a cubic is irreducible if and only if it has no root. Over $\Bbb F_2$, any polynomial satisfies: if $0$ is not a root, the constant term is nonzero; if $1$ is not a root, there are oddly many terms. For a cubic to be irreducible, both of these conditions must obtain. Thus the only irreducible cubics over $\Bbb F_2$ are $x^3+x+1$ and $x^3+x^2+1$ ( a cubic can not have five terms). – Lubin Apr 21 '18 at 3:35
• @Lubin: I completely agree with both your comments. Cheers! – Robert Lewis Apr 21 '18 at 3:36