Composed products and factors of cyclotomic polynomials over finite fields
详细信息 查看全文
- 作者：Aleksandr Tuxanidy (1)
Qiang Wang (1) - 关键词：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
- 刊名：Designs, Codes and Cryptography
- 出版年：2013
- 出版时间：November 2013
- 年：2013
- 卷：69
- 期：2
- 页码：203-231
- 全文大小：355KB
- 参考文献：1. Apostol T.M.: Introduction to analytic number theory. Springer, New York (1976) CrossRef
2. Bamunoba A.S.: Cyclotomic polynomials, African institute for mathematical sciences, Stellenbosch University, South Africa. Available at: http://users.aims.ac.za/~bamunoba/bamunoba.pdf (2010).
3. Berlekamp E.R.: Bit-serial Reed-Solomon Encoders. IEEE Trans. Inf. Theory 28, 869-74 (1982) CrossRef
4. Beyl F.R.: Cyclic subgroups of the prime residue group. Am. Math. Monthly 84, 46-8 (1977) CrossRef
5. Blake I., Gao S., Mills D.: Factorization of polynomials of the type / f ( / x / t ). Presented at the International Conference on Finite Fields, Coding Theory, and Advances in Comm. and Computing, Las Vegas (1991).
6. Brawley J.V., Carlitz L.: Irreducibles and the composed product for polynomials over a finite field. Discret. Math. 65, 115-39 (1987) CrossRef
7. Brawley J.V., Gao S., Mills D.: Computing composed products of polynomials. In: Finite fields: theory, applications, and algorithms (Waterloo, ON, 1997), Contemporary Mathematics, 225, pp. 1-5, American Mathematical Society, Providence (1997).
8. Cohen S.D.: On irreducible polynomials of certain types in finite fields. Proc. Camb. Philos. Soc 66, 335-44 (1969) CrossRef
9. Cohen S.D.: Explicit theorems on generator polynomials over finite fields. Finite Fields Appl 11, 337-57 (2005) CrossRef
10. Fitzgerald R.W., Yucas J.L.: Factors of Dickson polynomials over finite fields. Finite Fields Appl. 11(4), 724-37 (2005) CrossRef
11. Fitzgerald R.W., Yucas J.L.: Explicit factorization of cyclotomic and Dickson polynomials over finite fields. Arithmetic of Finite Fields. Lecture Notes in Computer Science 4547, pp. 1-0. Springer, Berlin, (2007).
12. Gao Z., Fu F.: The minimal polynomial over ${\mathbb {F}_{\rm q}}$ of linear recurring sequence over ${\mathbb{F}_{q^m}}$ . Finite Fields Appl. 15(6), 774-84 (2009) CrossRef
13. Golomb S., Gong G.: Signal design for good correlation: For wireless communication, cryptography, and radar. Cambridge University Press, Cambridge (2005).
14. Kyuregyan M.K., Kyureghyan G.H.: Irreducible compositions of polynomials over finite fields. Des. Codes Cryptogr. 61(3), 301-14 (2011) CrossRef
15. Lidl R., Niederreiter H.: Finite fields, In: Encyclopedia of mathematics and its applications, 2nd edn., vol. 20, Cambridge University Press, Cambridge (1997).
16. Meyn H.: Factorization of the cyclotomic polynomials / x 2^ / n +? 1 over finite fields. Finite Fields Appl. 2, 439-42 (1996) CrossRef
17. Mills D.: Factorizations of root-based polynomial compositions. Discret. Math. 240(1-), 161-73 (2001) CrossRef
18. Nicholson W.K.: Introduction to abstract Algebra, 2nd edn., Wiley (1999)
19. Selmer E.S.: Linear recurrence relations over finite fields. University of Bergen, Norway (1966)
20. Stein G.: Using the theory of cyclotomy to factor cyclotomic polynomials over finite fields. Math. Comp. 70(235), 1237-251 (2001) CrossRef
21. Sury B.: Cyclotomy and cyclotomic polynomials: The story of how Gauss narrowly missed becoming a philologist. Resonance. 4(12), 41-3 (1999) CrossRef
22. Tuxanidy A.: Composed products and factorization of cyclotomic polynomials over finite fields. Honours Project, Carleton University (2011)
23. Varshamov R.: A general method of synthesizing irreducible polynomials over Galois fields. Soviet Math. Dokl. 29, 334-36 (1984)
24. Wan Z.: Lectures on finite fields and Galois rings. World Scientific Publishing Co. Pte. Ltd. (2003).
25. Wang M., Blake I.F.: Bit-serial multiplication in finite fields. IEEE Trans. Comput. 38, 1457-460 (1989) CrossRef
26. Wang L., Wang Q.: On explicit factors of cyclotomic polynomials over finite fields. Des. Codes Cryptogr. 63, 87-04 (2011) CrossRef
27. Washington L.C.: Introduction to cyclotomic fields. Springer, New York (1982) CrossRef
28. Zierler N., Mills W.H.: Products of linear recurring sequences. J. Algebra 27, 147-57 (1973) CrossRef - 作者单位：Aleksandr Tuxanidy (1)
Qiang Wang (1)
1. School of Mathematics and Statistics, Carleton University, 1125 Colonel By Drive, Ottawa, ON, K1S 5B6, Canada
文摘
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 ≥? 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-36, 1984).