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?
 A: 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.
