Irreducible quadratic polynomial with coefficients in GF(16) with non-binary coefficients

Question

Q: Find an irreducible quadratic polynomial with coefficients in GF(16), with at least one non-binary coefficient.

A: We can’t because all quadratic polynomial with coefficients in GF(16) has a coefficient of either 0 or 1.

My prof said there is an equation for that so there exists an irreducible quadratic polynomial with at lest one non-binary coefficient. Can someone please give me a hint?

Answer 1

Let's try to find a polynomial without roots of the form $x^2 + c x + 1$ ( note that $x^2 + c x + d$ has roots if and only if $x^2 + \frac{c}{\sqrt{d}} + 1$ does). So now we need some $c$ that is not of the form $t + \frac{1}{t}$ with $t$ in the field. We'll be using the generator of the field provided by Jyrki. So let $\alpha \in GF(2^4)$ be a root of $x^4 + x + 1 = 0$. We have

$\alpha^4 + \alpha = 1$ so multiplying by $\alpha^5$ we get $\alpha^9 + \alpha^6 = \alpha^5$. Now raise to the square and get $\alpha^3 + \alpha^{12} = \alpha^{10}$. (raising again to the square returns to the start).

Now multiply $\alpha + 1 = \alpha^4$ by $\alpha^7$ and get $\alpha^8 + \alpha^7 = \alpha^{11}$. We can now take some squares: $\alpha^1 + \alpha^{14} = \alpha^{7}$, $\alpha^{2} + \alpha^{13} = \alpha^{14}$, $\alpha^{4} + \alpha^{11} = \alpha^{13}$. We still have to check two values: $\alpha^{0} + \alpha^{0} = 0$ and $\alpha^{5} + \alpha^{10}$. The last one is invariant under raising to the square, so it must be $1 = \alpha^{0}$. So here is a little table \begin{eqnarray} \alpha^{0} + \alpha ^{0} & =& 0\\ \alpha^{1} + \alpha^{14} & = & \alpha^7\\ \alpha^{2} + \alpha^{13} &=& \alpha^{14}\\ \alpha^{3} + \alpha^{12} & = & \alpha^{10}\\ \alpha^{4} + \alpha^{11}& = & \alpha^{13} \\ \alpha^{5} + \alpha^{10} & = & \alpha^{0}\\ \alpha^{6} + \alpha^{9} & = & \alpha^{5} \\ \alpha^{7} + \alpha^{8} & = & \alpha^{11} \end{eqnarray}

We can choose for instance $\alpha^{1}$ which is not of the form $t + \frac{1}{t}$, $t \in GF(2^4)$, so $x^2 + \alpha x + 1$ is irreducible.

Answer 2

A quick solution using the properties of the trace map is the following. Let $\alpha\in GF(16)$ be a zero of the polynomial $p(x):=x^4+x+1\in GF(2)[x]$ (hopefully known to be irreducible. Then $1/\alpha$ is a zero of the reciprocal polynomial $x^4p(1/x)=x^4+x^3+1$. It follows that the trace of $1/\alpha$ is equal to $1$.

Therefore the quadratic polynomial $$ m(x)=x^2+x+1/\alpha\in GF(16)[x] $$ fits the bill:

• $1/\alpha$ is not an element of $GF(2)$, so $m(x)$ is not binary.
• If $\beta\in GF(16)$ were a zero of $m(x)$, then we run into the following contradiction: $tr(\beta)=tr(\beta^2)$, so $tr(\beta+\beta^2)=0$ irrespective of whether $tr(\beta)$ is $0$ or $1$. Therefore $$tr(m(\beta))=tr(\beta^2)+tr(\beta)+tr(\frac1{\alpha})=tr(1/\alpha)=1,$$ implying that $m(\beta)$ cannot be zero. It follows that $m(x)$ is irreducible over $GF(16)$.