Composed products and factors of cyclotomic polynomials over finite fields
Let q = p s be a power of a prime number p and let Fq 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 Fq. In particular we obtain the explicit factorization of the cyclotomic polynomial Φ2n r over Fq where both r ≥ 3 and q are odd, gcd(q, r) = 1, and 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 Fq is given to us as a known. Let n = p1 e1p2 e2...ps es be the factorization of 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 pi ei are pairwise coprime, we show how to obtain the explicit factors of Φn from the factors of each p i 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)ordn(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 Fq and generalize a result due to Varshamov (Soviet Math Dokl 29:334-336, 1984).
|Keywords||Composed products, Construction of irreducible polynomials, Cyclotomic polynomials, Dickson polynomials, Factorization, Finite fields, Linear complexity, Linear feedback shift registers, Linear recurring sequences, Stream cipher theory|
|Journal||Designs, Codes and Cryptography|
Tuxanidy, A. (Aleksandr), & Wang, Q. (2013). Composed products and factors of cyclotomic polynomials over finite fields. Designs, Codes and Cryptography, 69(2), 203–231. doi:10.1007/s10623-012-9647-9