# Two questions on finite fields

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:

1. Irreducibility of $x^4+x+1$ over the prime field means that the roots of this polynomial are in $\Bbb{F}_{16}$. Now (inside an algebraic closure) $\Bbb{F}_{16}\cap\Bbb{F}_{64}=\Bbb{F}_4$. This means that if you factor $x^4+x+1$ over the field $\Bbb{F}_4$, then those factors will also reside in $\Bbb{F}_{64}[x]$. Undoubtedly (didn't check) the polynomials in $\alpha$ that show up are elements of $\Bbb{F}_{4}$. Identifying the elements of $\Bbb{F}_{64}$ that belong to the smaller field $\Bbb{F}_{4}$ takes a bit of calculation. The elements of that smaller field are third roots of unity, so I would try and calculate $\alpha^{21}$. Do you know how to factor $x^4+x+1$ over $\Bbb{F}_{4}$?
2. The short answer is that $\Bbb{F}_{7}[i]$ is the only field (up to isomorphism) that is a quadratic extension of $\Bbb{F}_{7}$. A somewhat longer answer is that since this is odd characteristic, you can apply the method of completing the square to find the zeros of any quadratic polynomial. If the discriminant is a square in $\Bbb{F}_{7}$, i.e. $D=b^2-4ac\in\{0,1,4,9=2\}$, then your polynomial has zeros in the prime field. OTOH if $D\in\{3,5,6\}$, then you need $\sqrt{D}$. But $\sqrt{6}=\sqrt{-1}$, and $3\equiv -25=(-1)\cdot 5^2\pmod7$, so $$\sqrt{3}=\sqrt{(-1)\cdot 5^2}=5\sqrt{-1}\in\Bbb{F}_{7}[i].$$ Similarly $$\sqrt{5}=\sqrt{-9}=3\sqrt{-1}\in \Bbb{F}_{7}[i].$$

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).

• Well, the usual problem in all characteristics except two is that the square root is two-valued ($\pm$). So technically I should not write things like $\sqrt3$ in a context, where we lack a mechanism of specifying one of the square roots. As this problem is already present in the meaning of $i$ here, I chose to ignore this non-uniqueness. It does not make a difference for the purposes of finding the roots of a quadratic in a given field. – Jyrki Lahtonen Dec 3 '13 at 7:52
• Thank you for your help, Jyrki. I have a couple questions. Re #1: What will identifying the elements of $F_{64}$ that belong to $F_4$ actually do for me, if $F_4$ is a contained within $F_{64}$? And how could you tell that the elements of $F_4$ are the third roots of unity? Finally, what would calculating $\alpha^{21}$ yield? And I'm unfortunately not clear on how to go about factoring polynomials, even over the smaller field $F_4$. I apologize for the flurry of questions! Re #2: This makes perfect sense. Thank you very much for your explanation. – thousandfoot Dec 3 '13 at 14:34
• @thousandfoot: I added a bit more to the first question. Sorry about being terse earlier. I wasn't sure how much help you wanted, and started with something minimal. – Jyrki Lahtonen Dec 3 '13 at 16:17
• I also added that more straightforward way of factoring $x^4+x+1$ over $\Bbb{F}_4$ as an example of using discrete log tables in this thread. – Jyrki Lahtonen Dec 3 '13 at 17:58