# Irreducible polynomial with LI roots

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?

• So you are looking for a normal basis! IIRC the Handbook of Cryptography describes an algorithm for finding a normal basis (one that is efficient for implementing field multiplication to boot). It is primarily intended for larger fields, and may not give the desired polynomial. – Jyrki Lahtonen Sep 18 '14 at 10:49
• You are asking for what is called a "normal basis". If you search on that term, you'll find a lot of work on it. You could start with en.wikipedia.org/wiki/Normal_basis --- why not see what you can learn about it, and then write up and post an answer to your question? – Gerry Myerson Sep 18 '14 at 10:49

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.

• The same argument goes thru whenever the degree of the field extension is a power of two. Otherwise the minimal polynomial of $F$ acting on $V$ has multiple irreducible factors, and they all need to be examined. – Jyrki Lahtonen Sep 18 '14 at 13:21
• Oh, and some roots of unity of order 257 have minimal polynomial $1+x+x^8+x^{15}+x^{16}$. Found by factoring $x^{257}-1$ with Mathematica. Roots of unity of order 257 have this nice property that their minimal polynomials all have degree sixteen. Furthermore they are all palindromic. – Jyrki Lahtonen Sep 18 '14 at 13:21
• This may be a tad overkill. I got excited and carried away :-/ – Jyrki Lahtonen Sep 18 '14 at 13:24
• Jyrki, we all love it when you get carried away and write up such detailed and carefully composed answers; it is by no means the first time :-) and I am most grateful for your efforts in so many instances. +1 of course. – Dilip Sarwate Sep 18 '14 at 13:33
• Thank you so much @Jyrki Lahtonen. – vijita Sep 19 '14 at 4:36