Name
Abstract | ||
|---|---|---|
Let q = p s be a power of a prime number p and let $${\mathbb {F}_{\rm 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 $${\mathbb {F}_{\rm q}}$$ . In particular we obtain the explicit factorization of the cyclotomic polynomial $${\Phi_{2^nr}}$$ over $${\mathbb {F}_{\rm q}}$$ where both r 驴 3 and q are odd, gcd(q, r) = 1, and $${n\in \mathbb{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 $${\Phi_r}$$ over $${\mathbb {F}_{\rm q}}$$ is given to us as a known. Let $${n = p_1^{e_1}p_2^{e_2}\cdots p_s^{e_s}}$$ be the factorization of $${n \in \mathbb{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^{e_i}}$$ are pairwise coprime, we show how to obtain the explicit factors of $${\Phi_{n}}$$ from the factors of each $${\Phi_{p_i^{e_i}}}$$ . We also demonstrate how to obtain the factorization of $${\Phi_{mn}}$$ from the factorization of $${\Phi_n}$$ when q is a primitive root modulo m and $${{\rm gcd}(m, n) = {\rm gcd}(\phi(m),{\rm ord}_n(q)) = 1.}$$ Here $${\phi}$$ 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 $${\mathbb {F}_{\rm q}}$$ and generalize a result due to Varshamov (Soviet Math Dokl 29:334---336, 1984). |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1007/s10623-012-9647-9 | Des. Codes Cryptography |
Keywords | Field | DocType |
Factorization,Composed products,Cyclotomic polynomials,Construction of irreducible polynomials,Dickson polynomials,Linear recurring sequences,Linear feedback shift registers,Linear complexity,Stream cipher theory,Finite fields,11T06,11B37,12Y05,94A60 | Discrete mathematics,Combinatorics,Finite field,Prime number,Cyclotomic polynomial,Multiplicative order,Factorization,Coprime integers,Primitive root modulo n,Mathematics,Euler's totient function | Journal |
Volume | Issue | ISSN |
69 | 2 | 0925-1022 |
Citations | PageRank | References |
5 | 0.60 | 13 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Aleksandr Tuxanidy | 1 | 13 | 1.83 |
| Qiang Wang | 2 | 237 | 37.93 |