I have to find a generator of the multiplicative group $GF(16)$. Where $GF(p)$ denotes a finit field with $p$ elements.
The problem here is, that 16 isn't prime.
I'm gonna solve it and just write all my questions when they appear.
Solution:
We know that $GF(16)^*$ denotes a field with 16 elements. Since 16 isn't prime, we have a problem, since we have zero-dividers in $GF(16)$. [e.g. 8+8 mod 16 = 0] So we need more elements.
I think the basic idea here is to switch to another field which is isomorphic to get more elements. [That's very unclear though].
We first note that the order of $GF(16)*$ is $\varphi(16)=2³=8$ We also know, that the order of any subgroup divides the order of the group, so:
$ord(a)\in \{1,2,4,8\} \ \ \forall a\in GF(16)*$
So we are looking for $a$ which fullfil $a^2\neq 1, a^4\neq 1$ or $a^8=1$. Since $a^2=a^4$ if $a^2=1$ we can just check for $a^4\neq 1$ to find a generator.
Now, the question is, what are our a's?
Because we have $16=2^4$ we can switch to $GF(2)[x]$ and look for a irreducible polynomial of order 4. I see why we need a irreducible polynomial (otherwise we don't have a field) but I don't exactly see why we can switch to $GF(2)$ and why we need a polynomial of degree 4.
Anyway, let's go ahead. So we are looking for a irreducible polynomial of degree 4. Let's take $x^4 + x^3 + 1=m(x)$. I found it by just trying it out, guess that's the only thing one can do.
So we are now looking for a generator for $GF(2)[x]_{x^4+x^3+1}$
We know that we need a polynomial $a(x)$ which fullwills $a(x)^4\not\equiv_{m(x)} 1$
Again, no idea how to do that other than just trying it out. Anyway, we would, by just trying it out, find such an $a(x)$ which then would be our generator.
So, my questions are:
Question 1: Why can we switch from $GF(16)$ to $GF(2)[x]_{m(x)}$. Question 2. How can we systematically and easily find $m(x)$ Question 3: How can we systematically and easily find $a(x)$?
Take any irreducible quartic in $\;\Bbb F_2[x]\;$ , say $\;p(x)=x^4+x+1\;$ . Then in fact
$$GF(16)=\Bbb F_{2^4}\cong \Bbb F_2[x]/\langle p(x)\rangle$$
and thus we can denote every element in $\;\Bbb F_{16}\;$ as a polynomial of degree at most three in $\;w\;$, where $\;w\;$ is any root of $\;p(x)\;$ . For example, we could take $\;w=x+\langle p(x)\rangle \in \Bbb F_2[x]/\langle p(x)\rangle\;$ . Of course, all the operations carried on in these algebraic structures are done $\;\pmod 2\;$ .
For example, with the above $\;w\;$:
$$w^5=w(w^4)=w(w+1)=w^2+w\neq1\,,\;\;w^3\neq1$$
...and we're done, since the order of $\;w\;$ in $\;\Bbb F_{16}^*\;$ must be a divisor of $\;\left|\Bbb F_{16}^*\right|=15\;$ ,and it isn't $\;3\;$ or $\;5\;$ (and obviously it isn't $\;1\;$ , either) , thus it must be $\;15\;$ , so $\;\Bbb F_{16}^*=\langle w\rangle\;$