×

An asymptotic formula for the number of irreducible transformation shift registers. (English) Zbl 1330.05018

Summary: We consider the problem of enumerating irreducible transformation shift registers. We give an asymptotic formula for the number of irreducible transformation shift registers in some special cases. Moreover, we derive a short proof for the exact number of irreducible transformation shift registers of order two using a recent generalization of a theorem of Carlitz.

MSC:

05A16 Asymptotic enumeration
94A55 Shift register sequences and sequences over finite alphabets in information and communication theory
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
15B33 Matrices over special rings (quaternions, finite fields, etc.)
12E20 Finite fields (field-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Ahmadi, O., Generalization of a theorem of Carlitz, Finite Fields Appl., 17, 473-480 (2011) · Zbl 1246.11181
[2] Bourbaki, N., Algèbre (1981), Masson: Masson Paris, Chapitres 4 à 7 · Zbl 0498.12001
[3] Carlitz, L., Some theorems on irreducible reciprocal polynomials over a finite field, J. Reine Angew. Math., 227, 212-220 (1967) · Zbl 0155.09801
[4] Chen, E.; Tseng, D., The splitting subspace conjecture, Finite Fields Appl., 24, 15-28 (2013) · Zbl 1286.05007
[5] Cohen, S. D., The distribution of polynomials over finite fields, Acta Arith., 17, 255-271 (1970) · Zbl 0209.36001
[6] Cohen, S. D., Uniform distribution of polynomials over finite fields, J. Lond. Math. Soc. (2), 6, 93-102 (1972) · Zbl 0253.12019
[7] Cohen, S. D., Some function field estimates with applications, (Number Theory and Its Applications. Number Theory and Its Applications, Ankara, 1996. Number Theory and Its Applications. Number Theory and Its Applications, Ankara, 1996, Lect. Notes Pure Appl. Math., vol. 204 (1999), Dekker: Dekker New York), 23-45 · Zbl 0930.11041
[8] Dewar, M.; Panario, D., Linear transformation shift registers, IEEE Trans. Inform. Theory, 49, 2047-2052 (2003) · Zbl 1262.94018
[9] Dewar, M.; Panario, D., Mutual irreducibility of certain polynomials, (Finite Fields and Applications. Finite Fields and Applications, Lecture Notes in Comput. Sci., vol. 2948 (2004), Springer: Springer Berlin), 59-68 · Zbl 1057.94010
[10] Ghorpade, S. R.; Hasan, S. U.; Kumari, M., Primitive polynomials, Singer cycles, and word oriented linear feedback shift registers, Des. Codes Cryptogr., 58, 123-134 (2011) · Zbl 1263.11108
[11] Ghorpade, S. R.; Ram, S., Block companion Singer cycles, primitive recursive vector sequences, and coprime polynomial pairs over finite fields, Finite Fields Appl., 17, 461-472 (2011) · Zbl 1263.11112
[12] Golomb, S. W.; Gong, G., Signal Design for Good Correlation (2005), Cambridge University Press · Zbl 1097.94015
[13] Hasan, S. U.; Panario, D.; Wang, Q., Word-oriented transformation shift registers and their linear complexity, (Proceedings of SEquences and Their Applications. Proceedings of SEquences and Their Applications, SETA 2012. Proceedings of SEquences and Their Applications. Proceedings of SEquences and Their Applications, SETA 2012, Lecture Notes in Comput. Sci., vol. 7280 (2012), Springer: Springer Berlin), 190-202 · Zbl 1304.94026
[14] Jacobson, N., Basic Algebra I (1985), W.H. Freeman: W.H. Freeman New York · Zbl 0557.16001
[15] Lidl, R.; Niederreiter, H., Finite Fields (1997), Cambridge University Press: Cambridge University Press Cambridge
[16] Niederreiter, H., The multiple-recursive matrix method for pseudorandom number generation, Finite Fields Appl., 1, 3-30 (1995) · Zbl 0823.11041
[17] Preneel, B., Introduction to the Proceedings of the Second Workshop on Fast Software Encryption, Lecture Notes in Comput. Sci., vol. 1008, 1-5 (1995), Springer: Springer Berlin
[18] Ram, S., Enumeration of linear transformation shift registers, Des. Codes Cryptogr., 75, 301-314 (2015) · Zbl 1331.94046
[19] Reiner, I., On the number of matrices with given characteristic polynomial, Illinois J. Math., 5, 324-329 (1961) · Zbl 0098.01402
[20] Tsaban, B.; Vishne, U., Efficient feedback shift registers with maximal period, Finite Fields Appl., 8, 256-267 (2002) · Zbl 1015.94005
[21] Zeng, G.; Han, W.; He, K., Word-oriented feedback shift register: \(σ\)-LFSR, (Cryptology ePrint Archive: Report 2007/114)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.