We provide an efficient algorithm deciding chaos for linear cellular automata (LCA) over (Z/mZ)^n, a large and important class of cellular automata (CA) which may exhibit many of the complex features typical of general CA and are used in many applications. The efficiency of our algorithm is mainly due to fact that it avoids the computation of the prime factor decomposition of m which is a well-known difficult task. Instead of factoring m we make use of a new and efficient generalized technique for computing the greatest common divisor (gcd) of polynomials with coefficients not belonging to a field, which in itself is an interesting result. We wish also to emphasize that the gcd computations required by our algorithm always involve polynomials of degree at most n. We also illustrate the impact of our algorithm in real-world applications regarding the growing domain of cryptosystems, the latter being often based on LCA over (Z/mZ)^n with n>1. As a matter of facts, since cryptosystems have to satisfy the so-called confusion and diffusion properties (which are ensured if the involved LCA is chaotic) our algorithm turns out to be an important tool for building chaotic LCA over (Z/mZ)^n and, hence, for improving the existing methods based on them.

Dennunzio, A., Formenti, E., Margara, L. (2024). An Efficient Algorithm Deciding Chaos for Linear Cellular Automata over (Z/mZ)n with Applications to Data Encryption. INFORMATION SCIENCES, 657, 1-12 [10.1016/j.ins.2023.119942].

An Efficient Algorithm Deciding Chaos for Linear Cellular Automata over (Z/mZ)n with Applications to Data Encryption

Margara, Luciano
2024

Abstract

We provide an efficient algorithm deciding chaos for linear cellular automata (LCA) over (Z/mZ)^n, a large and important class of cellular automata (CA) which may exhibit many of the complex features typical of general CA and are used in many applications. The efficiency of our algorithm is mainly due to fact that it avoids the computation of the prime factor decomposition of m which is a well-known difficult task. Instead of factoring m we make use of a new and efficient generalized technique for computing the greatest common divisor (gcd) of polynomials with coefficients not belonging to a field, which in itself is an interesting result. We wish also to emphasize that the gcd computations required by our algorithm always involve polynomials of degree at most n. We also illustrate the impact of our algorithm in real-world applications regarding the growing domain of cryptosystems, the latter being often based on LCA over (Z/mZ)^n with n>1. As a matter of facts, since cryptosystems have to satisfy the so-called confusion and diffusion properties (which are ensured if the involved LCA is chaotic) our algorithm turns out to be an important tool for building chaotic LCA over (Z/mZ)^n and, hence, for improving the existing methods based on them.
2024
Dennunzio, A., Formenti, E., Margara, L. (2024). An Efficient Algorithm Deciding Chaos for Linear Cellular Automata over (Z/mZ)n with Applications to Data Encryption. INFORMATION SCIENCES, 657, 1-12 [10.1016/j.ins.2023.119942].
Dennunzio, Alberto; Formenti, Enrico; Margara, Luciano
File in questo prodotto:
File Dimensione Formato  
1-s2.0-S002002552301527X-main.pdf

accesso aperto

Tipo: Versione (PDF) editoriale
Licenza: Licenza per Accesso Aperto. Creative Commons Attribuzione (CCBY)
Dimensione 598.05 kB
Formato Adobe PDF
598.05 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/952456
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? 5
social impact