Constructing sub-fields of a finite field Given a finite field $\mathbb{F}_{p^m}$ that is given $p$ and the irreducible polynomial of degree $m$. I want to construct irreducible polynomials of degree $d|m$. 
Let $\mathbb{F}_{p^m}= \mathbb{F}_{p}(\alpha)$, then we can take its partial trace or norm such that $ \beta :=Tr(\alpha) \in \mathbb{F}_{d} $. Note that we can find trace/Norm using Frobenius.
Now if can construct min poly of $\beta$ then we can get the required irreducible polynomial.
Does this idea work ?? I am unable to prove it. Is there any simple solution for this ?
 A: You need to exercise a bit of care, but the basic idea is fine.
What can go wrong is that $tr^m_d(\alpha)$ may land in too small a field. In other words, it may happen that the extension degree $[\Bbb{F}_p(\beta):\Bbb{F}_p]$ is a proper factor of $d$. The same thing may happen, if you use the relative norm instead of the relative trace.
As examples of both these phenomenon let me proffer the following. Consider the field $\Bbb{F}_{16}=\Bbb{F}_2(\alpha)$ where $\alpha$ is a zero of the irreducible polynomial $x^4+x+1$. Assume that we want to produce an element
that generated the intermediate field $\Bbb{F}_4$. If we use the relative trace
$$
tr^4_2:\Bbb{F}_{16}\to\Bbb{F}_4, x\mapsto x^4+x,
$$
and the above element $\alpha$, then we see that
$$
\beta=tr^4_2(\alpha)=\alpha^4+\alpha=1.
$$
Thus $\Bbb{F}_2(\beta)=\Bbb{F}_2$, and $\beta$ failed to generate the intermediate field $\Bbb{F}_4$.
If we, instead, you the relative norm
$$
N^4_2:\Bbb{F}_{16}\to\Bbb{F}_4, x\mapsto x\cdot x^4=x^5,
$$
then the above choice of $\alpha$ actually works (this is because $\alpha$ is of order fifteen, so $N_4^2(\alpha)$ is of order three, and hence generates $\Bbb{F}_4$). But if we carelessly use, in the role of $\alpha$, a fifth root of unity $\gamma\in\Bbb{F}_{16}$, then obviously $N^4_2(\gamma)=1$, and we get that
$\Bbb{F}_2(\gamma)=\Bbb{F}_{16}$ but $\Bbb{F}_2(N^4_2(\gamma))=\Bbb{F}_2$.
What works in general is the following. Let $\alpha$ be a primitive element of 
$\Bbb{F}_{p^m}$, in other words, $\alpha$ is a generator of the multiplicative group $\Bbb{F}_{p^m}^*$ (warning: there are two notions of primitive in field theory, this is prevalent in the theory of finite fields, but there is another definition of primitivity elsewhere in field-theory that is at odds with this).
Then the relative norm 
$$
\beta=N^m_d(\alpha)=\prod_{i=0}^{m/d-1}\alpha^{p^{id}}
$$
is always a generator of the multiplicative group of the intermediate field $\Bbb{F}_{p^d}$. Consequently, the minimal polynomial of $\beta$ over $\Bbb{F}_p$ is of degree $d$.
Also, both the relative norm and the relative trace are surjective mappings from the bigger field to the intermediate field. Therefore the process you described always works for some elements $\alpha$. Actually it works for most elements of $\Bbb{F}_{p^m}$ for a suitable definition of most. The above intermediate field $\Bbb{F}_4$ probably gives you the lowest success rate, when using a random $\alpha$.

In a comment the OP asked for examples with $\gcd(m,p)=1$. Let us denote
$F=\Bbb{F}_{p^d}$, $E=\Bbb{F}_{p^m}$. The relative trace
$$
tr^E_F:E\to F, x\mapsto x+x^{p^d}+x^{p^{2d}}+\cdots+x^{p^{m-d}}
$$
is a surjective $F$-linear mapping. Therefore the kernel of $tr^E_F$ is
an $F$-subspace of $E$ of dimension $(m/d)-1$. In other words, there exist 
$p^{m-d}$ elements $x\in E$ with the property $tr^E_F(x)=0$. So when $d$ is relatively small, the number of elements with trace zero exceeds the number of elements in the union of proper subfields of $E$, because the latter number is strictly less that $\sum_{\ell\mid m}p^{m/\ell}$, where $\ell$ ranges over the prime factors of $m$.
Similarly, the kernel of the relative norm map has $(p^m-1)/(p^d-1)>p^{m-d}$
elements.
Given these observations there will be elements $\alpha$ such that $\Bbb{F}_p(\alpha)=E$ but $tr^E_F(\alpha)=0$. And also elements $\alpha$ such that $\Bbb{F}_p(\alpha)=E$ and $N^E_F(\alpha)=1$.
