Factoring polynomials of the form $f(x^n)\in {\mathbb{F}}_q[x]$

Abstract

Let $f(x)\in {\mathbb{F}}_q[x]$ be an irreducible polynomial of degree $m$ and exponent $e$, and $n$ be a positive integer such that ${\nu }_p(q-1)\ge {\nu }_p(e)+{\nu }_p(n)$ for all $p$ prime divisor of $n$. We show a fast algorithm to determine the irreducible factors of $f(x^n)$. We also show the irreducible factors in the case when $\mathrm{rad}(n)$ divides $q-1$ and $\gcd (m,n)=1$. Finally, using this algorithm we split $x^n-1$ into irreducible factors, in the case when $n=2^m{p}^t$ and $q$ is a generator of the group ${\mathbb{Z}}_{p^2}^{\ast }$.