Exploring the Roots and Generators of $g$ in $\mathbb{F}_{16}$

[evinda]

Hello! (Wave)

We consider the irreducible polynomial $g=y^4+y+1 \in \mathbb{F}_2[y]$ and let $b$ be a root of $g$.

I want to find all the roots of $g$ and also three generators of $\mathbb{F}_{16}^{\ast}$ as for the basis $\{1, b, b^2, b^3 \}$.

Given that $b$ is a root of $g$ we can see that $b+1$ is also a root.
But how can we find all the roots of $g$.
Is there a proposition that we could use given that we have already two roots?

In order to find the generators do we need to find elements in this field the order of which is $15$?
If so, how can we find them? (Thinking)

 

[Deveno]

We can start by computing powers of $b$, which might give a clue.

Since $x^4 + x + 1$ is irreducible and monic, it is the minimal polynomial for $b$ (so any polynomial expression in $b$'s with terms of $b^3$ and lower cannot be reduced).

Since $b$ is an element of a group of order $15$, its order must be $1,3,5$ or $15$.

Now $b \neq 1$ because $b$ is a root of $x^4 + x + 1$ and $1$ is not.

$b^3 \neq 1$, or else $x^4 + x + 1$ is not the minimal polynomial of $b$.

$b^5 = b(b^4) = b(b+1) = b^2 + b \neq 1$ (why?)

Thus $b$ must have order $15$ (lucky us!).

Now the generators of $\Bbb F_2$ are those powers $b^k$, where $\gcd(k,15) = 1$, namely:

$b^2$
$b^4 = b + 1$
$b^7 = b^3 + b + 1$
$b^8 = b^2 + 1$
$b^{11} = b^3 + b^2 + b$
$b^{13} = b^3 + b^2 + 1$
$b^{14} = b^3 + 1$.

Let's try dividing $x^4 + x + 1$ by $(x+1)(x+b+1) = x^2 + x + (b^2+b)$, and see what we get:

Since $x^2(x^2 + x + (b^2 + b)) = x^4 + x^3 + (b^2+b)x^2$, subtracting, we have a remainder of:

$x^3 + (b^2+b)x^2 + x + 1$.

Similarly: $x(x^2 + x + (b^2+b)) = x^3 + x^2 + (b^2+b)x$, and upon subtraction, we get a remainder of:

$(b^2+b+1)x^2 + (b^2+b+1)x + 1$.

Now $(b^2+b+1)(x^2 + x + (b^2+b)) = (b^2+b+1)x^2 + (b^2+b+1)x + (b^2+b+1)(b^2+b)$

$=(b^2+b+1)x^2 + (b^2+b+1)x + 1$, which when subtracted, gives a remainder of $0$.

Thus $x^4 + x + 1 = (x^2 + x + (b^2+b))(x^2 + x + (b^2+b+1))$

so our remaining two roots are roots of $x^2 + x + (b^2+b+1)$, if we call these $r_1,r_2$, then:

$r_1 + r_2 = 1$
$r_1r_2 = b^2 + b + 1$.

Now $b^2 + b + 1 = b^{10}$ (verify this!), so if $r_1 = b^m$, and $r_2 = b^n$, we know that:

$m+n = 10$ (mod $15$).

The pairs to check are (2,8), (3,7) and (12,13). We get lucky, (2,8) works:

$b^2(b^8) = b(b^2+1) = b^4 + b^2 = b^2 + b + 1$
$b^2 + b^8 = b^2 + b^2 + 1 = 1$.

We verify that $b^2$ and $b^2 +1$ are roots of $x^4 + x + 1$:

$(b^2)^4 + b^2 + 1 = b^8 + b^2 + 1 = 1 + 1 = 0$
$(b^2+1)^4 + (b^2+1) + 1 = [(b^2 + 1)^2]^2 + b^2 + 1 + 1 = [b^4 + 1]^2 + b^2 = [(b+1) + 1]^2 + b^2$
$= b^2 + b^2 = 0$.

(There may be an easier way to do this).

 

[evinda]

We can start by computing powers of $b$, which might give a clue.

You mean in order to find the order of $b$ ? (Thinking)

Since $x^4 + x + 1$ is irreducible and monic, it is the minimal polynomial for $b$ (so any polynomial expression in $b$'s with terms of $b^3$ and lower cannot be reduced).

How do we know that there is no irreducible and monic polynomial of less degree that has $b$ as a root? (Thinking)

Since $b$ is an element of a group of order $15$, its order must be $1,3,5$ or $15$.

Now $b \neq 1$ because $b$ is a root of $x^4 + x + 1$ and $1$ is not.

$b^3 \neq 1$, or else $x^4 + x + 1$ is not the minimal polynomial of $b$.

$b^5 = b(b^4) = b(b+1) = b^2 + b \neq 1$ (why?)

$b^2+b=1 \Rightarrow b^2+b+1=0 \Rightarrow b^2+b^4=0 \Rightarrow b=1 \text{ or } b=1$, which both can't be true.

Now the generators of $\Bbb F_2$ are those powers $b^k$, where $\gcd(k,15) = 1$, namely:

$b^2$
$b^4 = b + 1$
$b^7 = b^3 + b + 1$
$b^8 = b^2 + 1$
$b^{11} = b^3 + b^2 + b$
$b^{13} = b^3 + b^2 + 1$
$b^{14} = b^3 + 1$.

Why does it hold that the generators of $\Bbb F_2$ are those powers $b^k$, where $\gcd(k,15) = 1$?

Let's try dividing $x^4 + x + 1$ by $(x+1)(x+b+1) = x^2 + x + (b^2+b)$, and see what we get:

Could you explain to me why we divide $x^4 + x + 1$ by $(x+1)(x+b+1) = x^2 + x + (b^2+b)$?

 

[Deveno]

You mean in order to find the order of $b$ ? (Thinking)

Yep. Sometimes there's easier ways, but here $15$ isn't that big a number.

How do we know that there is no irreducible and monic polynomial of less degree that has $b$ as a root? (Thinking)

Because you stated the polynomial was irreducible over $\Bbb Z_2[x]$. You have to be careful, here-it matters *which* field you talk about irreducibilty over-$x^2 - 2$ is irreducible over $\Bbb Q$, but not $\Bbb R$.

$b^2+b=1 \Rightarrow b^2+b+1=0 \Rightarrow b^2+b^4=0 \Rightarrow b=1 \text{ or } b=1$, which both can't be true.

I don't understand what you're doing here-if $b^2 + b + 1 = 0$, then $f(x) = x^2 + x + 1$ is a (monic) polynomial for which $f(b) = 0$. This contradicts the irreducibility of $g$.

Let me explain a bit further:

Suppose, by way of showing a contradiction, that some *other* polynomial $f(x) \in \Bbb Z_2[x]$ was the minimal degree monic polynomial with $f(b) = 0$.

We can (since $F[x]$ is a Euclidean domain) write:

$g(x) = q(x)f(x) + r(x)$, where either $r(x) = 0$, or the degree of $r$ is strictly less than the degree of $f$.

Then (in $K = F$), $0 = g(b) = q(b)f(b) + r(b) = q(b)0 + r(b) = 0 + r(b) = r(b)$. We cannot have $r(b) = 0$ with $r(x) \neq 0$, because that contradicts the minimality of the degree of $f$. So we are forced to have $r(x) = 0$. But then:

$g(x) = q(x)f(x)$.

Since the degree of $f$ is less than the degree of $g$, and $\text{deg }g = \text{deg }q + \text{deg }f$, we must have $\text{deg }q > 1$, that is- $q(x)$ is not a unit (a non-zero constant polynomial). But then THAT means $g(x)$ is reducible, contradiction (do you see why $f(b) = 0$ means $f$ is not a unit, either?).

Why does it hold that the generators of $\Bbb F_2$ are those powers $b^k$, where $\gcd(k,15) = 1$?

Suppose $\gcd(k,15) = d > 1$. Then $15 = dt$ for some positive integer $t$, and $k = du$ for some positive integer $u$. Clearly, $t < 15$.

Thus $(b^k)^t = (b^{du})^t = b^{dut} = b^{dtu} = (b^{dt})^u = (b^{15})^u= 1^u= 1$. So $b^k$ in this case has order at most $t < 15$, so it cannot generate the whole group of non-zero elements. (EDIT: correction due to evinda)

On the other hand, suppose $\gcd(k,15) = 1$. This means we have integers $r,s$ with $kr + 15s = 1$. That is:

$(b^k)^r = b^{kr} = b^{rk} = (b^{rk})(1) = (b^{rk})(1)^s = (b^{rk})(b^{15})^s = (b^{rk})(b^{15s}) = b^{rk+15s} = b^1 = b$, so $b \in \langle b^k\rangle$, so $\langle b\rangle \subseteq \langle b^k\rangle$.

Since $b$ generates the entire multiplicative group, we have:

$\Bbb F_{16}^{\ast} = \langle b\rangle \subseteq \langle b^k\rangle \subseteq \Bbb F_{16}^{\ast}$

in other words $\langle b^k\rangle = \Bbb F_{16}^{\ast}$, that is $b^k$ is a generator.

Could you explain to me why we divide $x^4 + x + 1$ by $(x+1)(x+b+1) = x^2 + x + (b^2+b)$?

To find the quadratic that the other two roots of $x^4 + x + 1$ are roots of.

 

[evinda]

I don't understand what you're doing here-if $b^2 + b + 1 = 0$, then $f(x) = x^2 + x + 1$ is a (monic) polynomial for which $f(b) = 0$. This contradicts the irreducibility of $g$.

Previously I had to find the order of $b$ and $b+1$ and I used the fact that $b^4=-b-1=b+1$.
So this is wrong since we consider that we are in $\mathbb{F}_{16}^{\ast}$, right?

Let me explain a bit further:

Suppose, by way of showing a contradiction, that some *other* polynomial $f(x) \in \Bbb Z_2[x]$ was the minimal degree monic polynomial with $f(b) = 0$.

We can (since $F[x]$ is a Euclidean domain) write:

$g(x) = q(x)f(x) + r(x)$, where either $r(x) = 0$, or the degree of $r$ is strictly less than the degree of $f$.

Then (in $K = F$), $0 = g(b) = q(b)f(b) + r(b) = q(b)0 + r(b) = 0 + r(b) = r(b)$. We cannot have $r(b) = 0$ with $r(x) \neq 0$, because that contradicts the minimality of the degree of $f$.

So if we have $r(x) \neq 0$ there cannot be any $a$ such that $r(a)=0$, right?

So we are forced to have $r(x) = 0$. But then:

$g(x) = q(x)f(x)$.

Since the degree of $f$ is less than the degree of $g$, and $\text{deg }g = \text{deg }q + \text{deg }f$, we must have $\text{deg }q > 1$, that is- $q(x)$ is not a unit (a non-zero constant polynomial)

Why does it have to hold that $\text{deg }q > 1$ ?

Suppose $\gcd(k,15) = d > 1$. Then $15 = dt$ for some positive integer $t$, and $k = du$ for some positive integer $u$. Clearly, $t < 15$.

Thus $(b^k)^t = (b^{du})^t = b^{dut} = b^{dtu} = (b^{dt})^u = (b^{15})^t = 1^t = 1$. So $b^k$ in this case has order at most $t < 15$, so it cannot generate the whole group of non-zero elements.

Why are we looking for the generators of $\mathbb{F}_2$ ?

Also it should be like that: $(b^k)^t = (b^{du})^t = b^{dut} = b^{dtu} = (b^{dt})^u = (b^{15})^u = 1^u = 1$, right?

$\Bbb F_{16}^{\ast} = \langle b\rangle \subseteq \langle b^k\rangle \subseteq \Bbb F_{16}^{\ast}$

Why does it hold that $\langle b^k\rangle \subseteq \Bbb F_{16}^{\ast}$ ?

To find the quadratic that the other two roots of $x^4 + x + 1$ are roots of.

Could you explain it further to me?

 

[Deveno]

Previously I had to find the order of $b$ and $b+1$ and I used the fact that $b^4=-b-1=b+1$.
So this is wrong since we consider that we are in $\mathbb{F}_{16}^{\ast}$, right?

I still don't understand your argument, so I cannot say it's right or wrong-it's unclear what you are trying to say. It IS true that if $b^2 + b =1$ that $b^2 + b^4 = 0 \implies b^2 = 0$ or $1 + b^2 = (b+1)^2= 0$. Neither of these can be true: $b^2 = 0 \implies b = 0$, and $0$ is not a root of $x^4 + x + 1$, and $(b+1)^2 = 0 \implies b+1 = 0 \implies b = 1$, and $1$ is not a root of $x^4 + x + 1$.

So if we have $r(x) \neq 0$ there cannot be any $a$ such that $r(a)=0$, right?

Well, yes, but the point is the minimality of our posited $f$ makes $r(x) \neq 0$ impossible, while $r(x) = 0$ makes the irreducibility of $g$ impossible.

Why does it have to hold that $\text{deg }q > 1$ ?

Because if $g(x) \in F[x]$ is irreducible, then for any factorization: $g(x) = f(x)h(x)$, one of $f,h$ must be a unit.

Why are we looking for the generators of $\mathbb{F}_2$ ?

$\Bbb F_2 \cong \Bbb F_2[x]/\langle x^4 + x + 1\rangle$, the isomorphism is explcitly:

$a_0 + a_1b + a_2b^2 + a_3b^3 \leftrightarrow a_0 + a_1x + a_2x^2 + a_3x^3 + \langle x^4 + x + 1\rangle$

The fact that $x^4 + x + 1$ is irreducible, means that $\langle x^4 + x + 1\rangle$ is a maximal ideal of $\Bbb F_2[x]$, which means that $\Bbb F_2[x]/\langle x^4 + x + 1\rangle$ is a field, which has $16$ elements.

It is a theorem of finite fields, that any two finite fields of the same order are isomorphic.

Also it should be like that: $(b^k)^t = (b^{du})^t = b^{dut} = b^{dtu} = (b^{dt})^u = (b^{15})^u = 1^u = 1$, right?

Yes. I have corrected my post.

Why does it hold that $\langle b^k\rangle \subseteq \Bbb F_{16}^{\ast}$ ?

We are proceeding from the assumption that $b$ is the generator of $\Bbb F_{16}^{\ast}$, no?

So $b^k$, being an element of the (finite) cyclic group generated by $b$, itself must generated a finite subgroup of $\langle b\rangle$.

But $\langle b\rangle$ IS $\Bbb F_{16}^{\ast}$, as $b$ is a generator.

 

[evinda]

Can we compute the order of the elements $b$ and $b+1$ in $\mathbb{F}_{16}^{\ast}$ as follows?

Since $b$ is a root of $g$ we have $b^4+b+1=0 \Rightarrow b^4=-b-1 \Rightarrow b^4=b+1$.
The order of $b$ has to be a divisor of the order of the group, so it could be $1,3,5$ or $15$.

Obviously $b \neq 1$, so the order isn't $1$.

If the order would be $3$ we would have $b^3=1 \Rightarrow b^4=b$. But we have that $b^4=b+1 $ and so $b+1=b \Rightarrow 1=0$, contradiction.

Suppose that the order is $5$. Then $b^5=1 \Rightarrow b^4 b=1 \Rightarrow (b+1)b=0 \Rightarrow b^2+b=1 \Rightarrow b^2+b+1=0 \Rightarrow b^2+b^4=0 \Rightarrow b^2(1+b^2)=0 \Rightarrow b=0 \text{ or } b^2=-1=1 \Rightarrow b=0 \text{ or } b=1$.

Any of the last equalities can't hold. So the order isn't $5$, and so it is $15$.Or is this implication $b^2+b=1 \Rightarrow b^2+b+1=0$ wrong since we are in $\mathbb{F}_{16}^{\star}$ ?

 

[Deveno]

Can we compute the order of the elements $b$ and $b+1$ in $\mathbb{F}_{16}^{\ast}$ as follows?

Since $b$ is a root of $g$ we have $b^4+b+1=0 \Rightarrow b^4=-b-1 \Rightarrow b^4=b+1$.
The order of $b$ has to be a divisor of the order of the group, so it could be $1,3,5$ or $15$.

Obviously $b \neq 1$, so the order isn't $1$.

If the order would be $3$ we would have $b^3=1 \Rightarrow b^4=b$. But we have that $b^4=b+1 $ and so $b+1=b \Rightarrow 1=0$, contradiction.

Suppose that the order is $5$. Then $b^5=1 \Rightarrow b^4 b=1 \Rightarrow (b+1)b=0 \Rightarrow b^2+b=1 \Rightarrow b^2+b+1=0 \Rightarrow b^2+b^4=0 \Rightarrow b^2(1+b^2)=0 \Rightarrow b=0 \text{ or } b^2=-1=1 \Rightarrow b=0 \text{ or } b=1$.

Any of the last equalities can't hold. So the order isn't $5$, and so it is $15$.Or is this implication $b^2+b=1 \Rightarrow b^2+b+1=0$ wrong since we are in $\mathbb{F}_{16}^{\star}$ ?

No, it still holds because $16$ is a power of $2$, that is to say, $\Bbb Z_2$ is the prime field of $\Bbb F_{16}$, so it has characteristic $2$, which means that for any element $u \in\Bbb F_{16}$ we have:

$u + u = u1 + u1 = u(1 + 1) = u0 = 0$.

 

[evinda]

No, it still holds because $16$ is a power of $2$, that is to say, $\Bbb Z_2$ is the prime field of $\Bbb F_{16}$, so it has characteristic $2$, which means that for any element $u \in\Bbb F_{16}$ we have:

$u + u = u1 + u1 = u(1 + 1) = u0 = 0$.

So this way to find the order of the elements is also correct, right? (Happy)

Could you explain to me what we have to do in order to find all the roots of $g$ ?

We know that there are at most $4$ roots since the degree of $g$ is $4$, right?

 

[Deveno]

So this way to find the order of the elements is also correct, right? (Happy)

Could you explain to me what we have to do in order to find all the roots of $g$ ?

We know that there are at most $4$ roots since the degree of $g$ is $4$, right?

Well, the problem is, there's no "universal factoring algorithm". Think of it this way: factoring polynomials is much like factoring an integer into prime powers. This is known to be a "hard problem", so hard, in fact, that many computer security encryption routines are based on the fact that if a number is large enough, figuring out its prime factors takes "too much time" for a brute force method to be practical.

So what we are left with is: if $b$ is a root of $g(x)$, then we know $(x - b)|g(x)$.

This leaves us with a cubic to solve. There's $13$ more likely candidates for a root, if $u$ is one of them, then $g(u) = 0$.

You provided another root at the beginning of this post. So we know $(x - b)(x - (b+1))$ is a divisor of $g$. That leaves a quadratic to solve, for which there IS a known algorithm (we could have used the general algorithm for a cubic, but that would have probably been "too messy" in this case).

Or: we could just try all the expressions in $b$:

$a_0 + a_1b + a_2b^2 + a_3b^3$, with $a_i \in \Bbb F_2$.

We already know that we aren't looking for $0,1$ or $b$. Trial-and-error would give us the other $2$ roots we're looking for easily enough.

The moral of the story is: low-dimensional examples ($\Bbb F_{16}$ has dimension $4$ over $\Bbb F_2$) are easy enough-if our irreducible polynomial was of degree $64$, we'd have a much harder time.

There is, in this case, a slightly slicker way: We could look for the subfield $\Bbb F_4$. If we know that $b$ is a generator for $(\Bbb F_{16})^{\ast}$, then we know that $b^5$ is an element of order $3$ (which the generator of $(\Bbb F_4)^{\ast}$ must be).

Now $b^5 = b(b^4) = b(b+1) = b^2 + b$.

If this is in our 4-element subfield, then by closure, so is $b^5 + 1 = b^2 + b + 1$. So we just need to verify that:

$\{0,1,b^2+b,b^2+b+1\}$ is a field. Closure under addition is obvious, and the only product we need to check is:

$(b^2+b)(b^2 + b + 1) = b^4 + b^3 + b^2 + b^3 + b^2 + b = b^4 + b = b + 1 + b = 1$.

This simultaneously shows us that we have closure and that $\dfrac{1}{b^2 + b} = b^2 + b + 1$. So we have a subfield.

For notational convenience, let's call $b^2 + b = u$. So we are working in $\Bbb F_2$, now. Let's try to factor $g(x) = x^4 + x + 1$ over $\Bbb F_2$.

Since we know $(x - b)(x - (b + 1)) = (x+b)(x + (b+1)) = x^2 + x + b^2 + b = x^2 + x + u \in (\Bbb F_2)[x]$ is a factor, we know that the other factor must also lie in $(\Bbb F_2)[x]$. Say this factor is:

$x^2 + sx + t$, where $s,t \in \Bbb F_2$. Since $tu = 1$, we know $t = u + 1$ (verify that the minimal polynomial for $u$ is $x^2 + x + 1$, that is, $u$ is a primitive cube root of 1 over $\Bbb F_2$).

We also know that $s+1 = 0$ from:

$(x^2 + sx + t)(x^2 + x + u) = g(x)$, since the cubic term of $g(x)$ is 0.

Thus $s = 1$, so $g$ factors over $\Bbb F_2$ as:

$(x^2 + x + (u+1))(x^2 + x + u)$.

Thus the roots in $\Bbb F_2 = \Bbb F_{16}$ are roots of $x^2 + x + (u+1) = x^2 + x + (b^2 + b + 1)$, which is the same factor we found by polynomial division.

A slightly more advanced attack:

Any (field) automorphism of $\Bbb F{16}$ which fixes $\Bbb F_2$ must send a root of $g(x)$ to another root. Now the restriction of such an automorphism to the multiplicative group yields a group automorphism of $(\Bbb F_{16})^{\ast}$, which is cyclic of order $15$. Since an automorphism sends generators to generators, the other roots must be generators of the multiplicative group (primitive elements).

The automorphisms of the cyclic multiplicative group are:

$b \mapsto b$ (the identity automorphism)
$b \mapsto b^2$
$b \mapsto b^4 = b+1$ <---we already have this root.
$b \mapsto b^7 = b^3 + b + 1$
$b \mapsto b^8 = b^2 + 1$
$b \mapsto b^{11} = b^3 + b^2 + b$
$b \mapsto b^{13} = b^3 + b^2 + 1$
$b \mapsto b^{14} = b^3 + 1$

Now, not all of these (group) automorphisms will actually be field automorphisms, because some of them won't be ADDITIVE.

So let's check the map $b \mapsto b^2$:

$(a_0 + a_1b + a_2b^2 + a_3b^3) \mapsto (a_0 + a_1b^2 + a_2b^4 + a_3b^6)$

Now the image is $a_0 + a_1b^2 + a_2(b+1) + a_3(b^3 + b^2) = (a_0 + a_2) + a_2b + (a_1 + a_3)b^2 + a_3b^3$

which can be regarded as the $\Bbb F_2$-linear map $\Bbb F_2^4 \to \Bbb F_2^4$:

$(a_0,a_1,a_2,a_3) \mapsto (a_0+a_2,a_2,a_1+a_3,a_3)$, or by the matrix:

$\begin{bmatrix}1&0&1&0\\0&0&1&0\\0&1&0&1\\0&0&0&1\end{bmatrix} \in \text{Mat}_4(\Bbb F_2)$

(note this matrix is invertible).

Thus $b \mapsto b^2$ is an additive map, so this is a field automorphism, and so $b^2$ is a root of $g$ (so we've found a 3rd root).

Finally, we can compose the automorphisms $b \mapsto b + 1$, and $b \mapsto b^2$ to get our final automorphism, and root:

$b \mapsto b+1 \mapsto b^2 + 1$, that is, the set of roots is:

$\{b,b+1,b^2,b^2+1\}$.

Checking:

$(x + b)(x + (b+1))(x + b^2)(x + (b^2 + 1)) = (x^2 + (b+1)x + bx + b^2 + b)(x^2 + (b^2 + 1)x + b^2x + b^2(b^2+1))$

$= (x^2 + x + b^2 + b)(x^2 + x + b^2+b+1) = x^4 + x + 1 = g(x)$.

 

[evinda]

$b$ and $b+1$ are two generators of $\mathbb{F}_{16}^{\ast}$. How can we find a third one?
Do we have to check if $b^2$ or $b^2+1$ have order $15$?

 

[Deveno]

$b$ and $b+1$ are two generators of $\mathbb{F}_{16}^{\ast}$. How can we find a third one?
Do we have to check if $b^2$ or $b^2+1$ have order $15$?

Both of those questions were answered in post #2.

If you do feel like verifying that $b^2$ and $b^2+1$ have order 15, you can certainly do so.

As indicated before, it suffices to check that $(b^2)^3 \neq 1, (b^2)^5 \neq 1$ and $(b^2+1)^3 \neq 1, (b^2+1)^5 \neq 1$.

Because our base field has characteristic two, it's easiest to "expand powers of sums by squares". I'll get to that in a bit, but first we'll check the powers of $b^2$.

$(b^2)^3 = b^6 = (b^4)(b^2) = (b+1)b^2 = b^3 + b^2$.

Since $b$ is not a root of $x^3 + x^2 + 1$ (or else $x^4 + x + 1$ would not be the minimal polynomial of $b$ over $\Bbb F_2$, nor irreducible, since $x^3 + x^2 + 1$ would be a factor), we do not have:

$b^3 + b^2 + 1 = 0$, so $(b^2)^3 = b^3 + b^2 \neq 1$.

$(b^2)^5 = b^{10} = (b^5)^2 = (b(b+1))^2 = (b^2 + b)^2 = b^4 + b^2 = b^2 + b + 1$

Again, this is not equal to 1, since $b^2 + b = b(b+1) \neq 0$.

Thus $b^2$ has order 15. Again, all you really need here, is the fact that $\gcd(2,15) = 1$.

The fact that $b^2 + 1$ has order 15, derives directly from the fact that $b^2 + 1 = b^8$ and $\gcd(8,15) = 1$. But we can verify the other way:

$(b^2 + 1)^3 = (b^2 + 1)^2(b^2 + 1) = (b^4 + 1)(b+1) = (b + 1 + 1)(b^2 + 1) = b(b^2+1) = b^3 + b \neq 1$.

You may (or may not) find it entertaining to show that $(b^8)^3 = b^9$, which is, of course, not $1$ since $b$ has order $15$, and $9 < 15$.

$(b^2+1)^5 = [(b^2+1)^2]^2(b^2+1) = (b^4 + 1)^2(b^2+1) = (b+1+1)^2(b^2+1) = b^2(b^2+1) = b^4 + b^2 = b^2+b+1 \neq 1$.

Alternatively, you may show that $(b^8)^5 = b^{40} = b^{10} \neq 1$, since $10 < 15$ (note $b^{10} = b^2(b^8) = b^2(b^2+1) = b^4 + b^2 = b^2 + b + 1$, just as we obtained before).