Factoring polynomials of the form f(xn)∈Fq[x]

Let f(x)∈Fq[x] be an irreducible polynomial of degree m and exponent e. For each positive integer n, such that νp(q−1)≥νp(e)+νp(n) for all prime divisors p of n, we show a fast algorithm to determine the irreducible factors of f(xn). Using this algorithm, we give the complete factorization of xn−1 into irreducible factors in the case where n=dpt, p is an odd prime, q is a generator of the group Zp2⁎ and either d=2m with m≤ν2(q−1) or d=ra, where r is a prime dividing q−1 but not p−1.