Constructing irreducible polynomials recursively with a reverse composition method

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{k}{t}}{\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.