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?

  • 1
    $\begingroup$ 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. $\endgroup$ – Jyrki Lahtonen Sep 18 '14 at 10:49
  • 1
    $\begingroup$ 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? $\endgroup$ – 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$.


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.

  • $\begingroup$ 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. $\endgroup$ – Jyrki Lahtonen Sep 18 '14 at 13:21
  • $\begingroup$ 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. $\endgroup$ – Jyrki Lahtonen Sep 18 '14 at 13:21
  • $\begingroup$ This may be a tad overkill. I got excited and carried away :-/ $\endgroup$ – Jyrki Lahtonen Sep 18 '14 at 13:24
  • $\begingroup$ 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. $\endgroup$ – Dilip Sarwate Sep 18 '14 at 13:33
  • $\begingroup$ Thank you so much @Jyrki Lahtonen. $\endgroup$ – vijita Sep 19 '14 at 4:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.