Irreducible polynomial with LI roots

Question

I am doing a small project under the domain cryptography. Recently I stuck with a problem in mathematics related to finite fields. My question is how can I found out irreducible polynomial(or primitive polynomial), irreducible in GF(2), with linearly independent roots for an extended field of $GF(2^{16})$ and is there any generalised method for finding it for a higher field size?

Answer 1

This is a bit subtle as relatively special properties of this field come to the fore in my solution. Therefore I won't settle with a generic hint. Something simpler is probably out there. Anyway, on with it.

Recall that the trace function of $GF(2^{16})$ is defined as $$ tr(x)=x+x^2+x^4+x^8+\cdots+x^{32768}=\sum_{i=0}^{15}x^{2^i}. $$ If $F(x)=x^2$ is the Frobenius automorphism, then we can also write $tr(x)=\sum_{i=0}^{15}F^i(x)$. Also recall that an element $\alpha\in GF(2^{16})$ is said to generate a normal basis, if the elements $\alpha, F(\alpha), F^2(\alpha),\ldots,F^{15}(\alpha)$ form a basis of $GF(2^{16})$ as a vector space over $GF(2)$.

In this very special case we have the surprisingly simple characterization.

Lemma. An element $\alpha\in GF(2^{16})$ generates a normal basis if and only if $tr(\alpha)=1$.

Proof. (May go over your head if you are note conversant with the theory of modules over PIDs) We consider $GF(2^{16})$ as a module $V$ over the polynomial ring $GF(2)[\tau]$ by letting the indeterminate $\tau$ act as the Frobenius automorphism. This means that if $f(x)=a_0+a_1x+\cdots a_nx^n$ is a polynomial with coefficients in $GF(2)=\{0,1\}$ and that $v\in V$ is arbitrary, the module action is $$ f\cdot v:=\sum_{i=0}^n a_iF^i(v)=a_0v+a_1v^2+a_2v^4+\cdots+a_nv^{2^n}. $$

It is known that as a $GF(2)[\tau]$-module $V$ is cyclic. In fact we easily see that $V=GF(2)[\tau]\cdot v$ if and only if $v$ generates a normal basis. Details about this are included in the standard proof of existence of normal bases of finite fields. This is in many books. A crude on-site exposition is in my earlier answer. Anyway, we note that the existence of a normal basis means that $$V\cong GF(2)[\tau]/\langle \tau^{16}-1\rangle$$ as a $GF(2)[\tau]$-module.

This means that we need to look at submodules of $GF(2)[\tau]/\langle \tau^{16}-1\rangle$. Because $GF(2)[\tau]$ is a PID, such submodules are also cyclic and in 1-1 correspondence with the factors of $\tau^{16}-1$. Because $16$ is a power of two, repeated applications of the so called Freshman's dream tell us that $$ \tau^{16}-1=\tau^{16}+1=(\tau+1)^{16}. $$ This implies that all the proper factors of $\tau^{16}-1$ are factors of $(\tau+1)^{15}$. Consequently the unique maximal submodule of $V$ is $$ M=\{v\in V\mid (\tau+1)^{15}\cdot v=0\}. $$ The key is that $$ (\tau+1)^{15}=\sum_{i=0}^{15}\tau^i. $$ This follows easily by multiplying both sides by $\tau-1$ (or from binomial expansion aided by Lucas' theorem). Consequently $$ (\tau+1)^{15}\cdot v=tr(v) $$ for all $v\in V$. Thus $v\in M$ if and only if $tr(v)=0$.

Q.E.D.

How does this help you? If $\alpha$ is an element of $GF(2^{16})$ such that its minimal polynomial $m_\alpha(x)$ has degree sixteen, then $$ m_\alpha(x)=\prod_{i=0}^{15}(x-F^i(\alpha)). $$ Expanding this gives $$ m_\alpha(x)=x^{16}+tr(\alpha)x^{15}+\text{lower degree terms}. $$

Conclusion. Find an irreducible polynomial of degree 16 such that its degree 15 term is not zero. Then you are done.