evinda said:
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)$.