Logo image
Back
Chaos and ergodicity are decidable for linear cellular automata over (Z/mZ)(n)
Journal article   Peer reviewed

Chaos and ergodicity are decidable for linear cellular automata over (Z/mZ)(n)

Alberto Dennunzio, Enrico Formenti, Darij Grinberg and Luciano Margara
Information sciences, v 539, pp 136-144
01 Oct 2020
DOI: https://doi.org/10.1016/j.ins.2020.05.123
url
https://www.sciencedirect.com/science/article/pii/S002002552030548XView
Open

Abstract

Computer Science, Information Systems Science & Technology Computer Science Technology
We prove that important properties describing complex behaviours as ergodicity, chaos, topological transitivity, and topological mixing, are decidable for one-dimensional linear cellular automata (LCA) over (Z/mZ)(n) (Theorem 6 and Corollary 7), a large and important class of cellular automata (CA) which are able to exhibit the complex behaviours of general CA and are used in applications. In particular, we provide a decidable characterization of ergodicity, which is known to be equivalent to all the above mentioned properties, in terms of the characteristic polynomial of the matrix associated with LCA. We stress that the setting of LCA over (Z/mZ)(n )with n > 1 is more expressive, gives rise to much more complex dynamics, and is more difficult to deal with than the already investigated case n =1. The proof techniques from [23,25] used when n = 1 for obtaining decidable characterizations of dynamical and ergodic properties can no longer be exploited when n > 1 for achieving the same goal. Indeed, in order to get the decision algorithm (Algorithm 1) we need to prove a non trivial result of abstract algebra (Theorem 5) which is also of interest in its own. We also illustrate the impact of our results in real-world applications concerning the important and growing domain of cryptosystems which are often based on one-dimensional 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 (ensured by ergodicity and chaos, respectively, of the involved LCA) Algorithm *1 turns out to be an important tool for building chaotic/ergodic one-dimensional linear CA over (Z/mZ)(n) and, hence, for improving the existing methods based on them. (C) 2020 Elsevier Inc. All rights reserved.

Metrics

6 Record Views
15 citations in Web of Science
19 citations in Scopus

Details

InCites Highlights

Data related to this publication, from InCites Benchmarking & Analytics tool:

Collaboration types
Domestic collaboration
International collaboration
Web of Science research areas
Computer Science, Information Systems
Logo image