  We suggest a construction of the minimal polynomial $m_{\beta^k}$ of
$\beta^k\in \mathbb F_{q^n}$ over $\mathbb F_q$ from the minimal polynomial $f=
m_\beta$ for all positive integers $k$ whose prime factors divide $q-1$. The
computations of our construction are carried out in $\mathbb F_q$. The key
observation leading to our construction is that for $k \mid q-1$ holds
$$m_{\beta^k}(X^k) = \prod_{j=1}^{\frac kt} \zeta_k^{-jn} f (\zeta_k^j X),$$
where $t= \max \{m\mid \gcd(n,k): f (X) = g (X^m), g \in \mathbb F_q[X]\}$ and
$\zeta_{k}$ is a primitive $k$-th root of unity in $\mathbb F_q$. The
construction allows to construct a large number of irreducible polynomials over
$\mathbb F_q$ of the same degree. Since different applications require
different properties, this large number allows the selection of the candidates
with the desired properties.
