I'm having some difficult with finite fields. If someone could point out a direction in which to look for these, or link to relevant material online, I would really appreciate it! I'm asked to factor $x^4+x+1$ over $F_{2^6}$, or $F_{64}$. I'm not sure how to attack this problem. I know $x^4+x+1$ is irreducible over 2, and that $F_{64}$ is the splitting field of the degree 6 irreducible polynomial $x^6+x+1$. Then there exists some element $\alpha \in F_{64}-F_{2}$ such that $\alpha^6+\alpha+1=0$. But how do I apply this to factor $x^4+x+1$? Is there a general method to factoring over a field like this? Wolfram alpha's response is (slightly) offputting: $$x^4+x+1 = (\alpha^5+\alpha^4+\alpha^3+\alpha+x^2+x)(\alpha^5+\alpha^4+\alpha^3+\alpha+x^2+x+1)$$ where $\alpha$ satisfies $\alpha^6+\alpha+1=0$. Clearly, this is related to the $\alpha$ I've found. But how did they come up with the factors?
My second question is related to a complex extension of a finite field. We're asked to show that all polynomials $ax^2+bx+c \in F_7[x]$ have roots in $F_7(i)$, the extension of $F_7$ by a root of $x^2+1$. What avenue do I approach this by? What in Galois theory allows me to show that quadratics split over this extension?
Any tips would be appreciated. Thank you.
Hints/pointers/observations:
Fleshing out the scheme of attack on the first question. The point is that because $\Bbb{F}_{16}$ is a quadratic extension of $\Bbb{F}_4$, the minimal polynomial (over the prime field) of any element of $\Bbb{F}_{16}$, such as $x^4+x+1$ must then factor into at most quadratic factors.
To that end we need a better look at $\Bbb{F}_4$. This field is $\{0,1,\beta,\beta+1\}$, where $\beta$ is a primitive cubic root of unity. As $x^3-1=(x-1)(x^2+x+1)$ we see that $\beta$ is a zero of $\phi_3(x)=x^2+x+1$, the other zero being $\beta^2=\beta+1$. So at this point we know that in $\Bbb{F}_4[x]$ we have $$ \phi_3(x)=x^2+x+1=(x-\beta)(x-\beta-1)=(x+\beta)(x+\beta+1). $$ Next I cheat a bit. [We could do this in a more straightforward way, if we had a log-table of $\Bbb{F}_{16}$ at hand. I will add one as another question/answer, because that is useful for many questions, and the finite field tag wiki can then refer to that.] The cheating bit is to make the observation that $$ \phi_3(x^2+x)=(x^2+x)^2+(x^2+x)+1=(x^4+x^2)+(x^2+x)+1=x^4+x+1. $$ Thus the earlier factorization of $\phi_3(x)$ in $\Bbb{F}_4[x]$ gives rise to a factorization $$ x^4+x+1=\phi_3(x^2+x)=(x^2+x+\beta)(x^2+x+\beta+1). $$ If so minded, you can verify this factorization by expanding it out and using the relations $\beta(\beta+1)=\beta^2+\beta=1$.
But your question was about factoring $x^4+x+1$ in $\Bbb{F}_{64}[x]$. To that end we simply need to find the (unique) copy of $\Bbb{F}_{4}$ inside your field $\Bbb{F}_{64}=\Bbb{F}_2[\alpha]$, where $\alpha$ is a zero of $x^6+x+1$. IIRC it was given (or we can check it out while we calculate) that $x^6+x+1$ is a primitive polynomial, IOW the element $\alpha$ is a generator of the multiplicative group $\Bbb{F}_{64}^*$. So $\alpha$ is of order $63$. Thus $\alpha^{21}$ and $\alpha^{42}$ are cubic roots of unity, and thus they must be the elements $\beta$ and $\beta^2=\beta+1$. In some order, i.e. we have no way of telling which is which, and because an automorphism of $\Bbb{F}_4$ interchanges them, we don't particularly care!!
So, getting some dirt on our hands, we calculate $$ \begin{aligned} \alpha^7&=\alpha\cdot\alpha^6=\alpha(\alpha+1)=\alpha^2+\alpha,\\ \alpha^{21}&=(\alpha^7)^3=(\alpha^2+\alpha)^3=\alpha^6+\alpha^5+\alpha^4+\alpha^3+\alpha^2=\\ &=\alpha^5+\alpha^4+\alpha^3+\alpha^2+\alpha+1 \end{aligned} $$ using the minimal polynomial relation $\alpha^6=\alpha+1$ at selected points.
Anyway those ugly entities $\alpha^5+\alpha^4+\alpha^3+\alpha^2+\alpha+1$ and $\alpha^5+\alpha^4+\alpha^3+\alpha^2+\alpha$ are just the primitive third roots of unity in $\Bbb{F}_{64}$. This explains that the factorization given by WA is the same as the above factorization of $x^4+x+1$ over $\Bbb{F}_4$. Also, we can conclude that the set $$ K=\{0,1,\alpha^5+\alpha^4+\alpha^3+\alpha^2+\alpha+1,\alpha^5+\alpha^4+\alpha^3+\alpha^2+\alpha\} $$ is a subfield of $\Bbb{F}_{64}$ that is then also a copy of $\Bbb{F}_4$.
An isomorphism of fields $\Bbb{F}_4\to K\subset\Bbb{F}_{64}$ is to map $\beta\mapsto \alpha^5+\alpha^4+\alpha^3+\alpha^2+\alpha$, $\beta+1\mapsto \alpha^5+\alpha^4+\alpha^3+\alpha^2+\alpha+1$ (or the other way around).