Composed products and factors of cyclotomic polynomials over finite fields

摘要

Let q = p~s be a power of a prime number p and let F_q be a finite field with q elements. This paper aims to demonstrate the utility and relation of composed products to other areas such as the factorization of cyclotomic polynomials, construction of irreducible polynomials, and linear recurrence sequences over F_q. In particular we obtain the explicit factorization of the cyclotomic polynomial Φ_(2"r) over F_q where both r ≥ 3 and q are odd, gcd(q,r) = 1, and n ∈ N. Previously, only the special cases when r = 1, 3, 5, had been achieved. For this we make the assumption that the explicit factorization of Φ_r over F_q is given to us as a known. Let n = p_1~(e1) p_2~(e2) … p_s~(es) be the factorization of n ∈ N into powers of distinct primes p_i 1 ≤ i ≤ s. In the case that the multiplicative orders of q modulo all these prime powers p_i~(ei) are pairwise coprime, we show how to obtain the explicit factors of Φ_n from the factors of each Φ_(Pi)~(ei). We also demonstrate how to obtain the factorization of Φ_(mn) from the factorization of Φ_n when q is a primitive root modulo m and gcd(m, n) = gcd(Φ(m), ord_n(q)) = 1. Here Φ is the Euler's totient function, and ord_n(q) denotes the multiplicative order of q modulo n. Moreover, we present the construction of a new class of irreducible polynomials over F_q and generalize a result due to Varshamov (Soviet Math Dokl 29:334-336, 1984).