Composed products and factors of cyclotomic polynomials over finite fields (Q2391671)

Let \(q\) be a power of an odd prime and let \(\mathbb F_q\) the finite field with \(q\) elements. Let \(r\) be an odd integer with \((r,q)=1\). Explicit factorizations of the cyclotomic polynomials \(Q_{2^nr}(x)\) into irreducible polynomials over \(\mathbb F_q\) have been given by for \(r=1\) [\textit{H. Meyn}, Finite Fields Appl. 2, No. 4, 439--442 (1996; Zbl 0912.11053)], \(r=3\) [the reviewer and \textit{J. L. Yucas}, Arithmetic of finite fields. WAIFI 2007, Madrid, 2007. Lect. Notes Comput. Sci. 4547, 1--10 (2007; Zbl 1235.11109)] and \(r=5\) [the second author and \textit{L. Wang}, Des. Codes Cryptography 63, No. 1, 87--104 (2012; Zbl 1260.11074)]. Here the general case is done. The coefficients of the irreducible factors come from the factors of \(Q_r(x)\) plus solutions to certain systems of nonlinear recurrence relations. The key to the proofs is the notion of a composed product. Given polynomials \(f\) and \(g\), the composed product is: \[ f\odot g =\prod_{\alpha}\prod_{\beta} (x-\alpha\beta), \] where \(\alpha\) runs over the roots of \(f\) and \(\beta\) over the roots of \(g\). Then \(Q_{2^nr}=Q_{2^n}\odot Q_r\). Thus previous results on factoring composed products can be applied.