Analysis and computation of multidimensional linear complexity of periodic arrays

• Published in: Designs, codes, and cryptography codes, and cryptography, 2024-03, Vol.92 (3), p.709-722
• Main Authors: Arce, Rafael, Hernández, Carlos, Ortiz, José, Rubio, Ivelisse, Torres, Jaziel
• Format: Article
• Language: English
• Subjects: Arrays; Asymptotic methods; Asymptotic properties; Coding and Cryptography 2022; Coding and Information Theory; Complexity; Computer Science; Cryptology; Discrete Mathematics in Computer Science; Information theory; Open source software; Patent applications
• ISSN: 0925-1022; 1573-7586
• DOI: 10.1007/s10623-023-01274-w

Linear complexity is an important parameter for arrays that are used in applications related to information security. In this work we survey constructions of two and three dimensional arrays, and present new results on the multidimensional linear complexity of periodic arrays obtained using the definition and method proposed in Arce-Nazario et al. (Appl. Algebra Eng Commun Comput 31(1):43–63, 2020), Gomez-Perez et al. (2015 IEEE International Symposium on Information Theory, pp 2697–2701, 2015) and Moreno et al. (US Provisional Patent Applications, 2015). The results include a generalization of a bound for the linear complexity, a comparison with the measure of complexity for multisequences, and computations of the complexity of arrays with periods that are not relatively prime for which the “unfolding method” does not work. Conjectures for exact formulas and the asymptotic behavior of the complexity of some array constructions are formulated. We also present open source software for constructing multidimensional arrays and for computing their multidimensional linear complexity.