Enumeration of Maximal Cycles Generated by Orthogonal Cellular Automata

Author name not available (Why is that?)

Publication date: 5 March 2022

Abstract: Cellular Automata (CA) are an interesting computational model for designing Pseudorandom Number Generators (PRNG), due to the complex dynamical behavior they can exhibit depending on the underlying local rule. Most of the CA-based PRNGs proposed in the literature, however, suffer from poor diffusion since a change in a single cell can propagate only within its neighborhood during a single time step. This might pose a problem especially when such PRNGs are used for cryptographic purposes. In this paper, we consider an alternative approach to generate pseudorandom sequences through emph{orthogonal CA} (OCA), which guarantees a better amount of diffusion. After defining the related PRNG, we perform an empirical investigation of the maximal cycles in OCA pairs up to diameter

d = 8

. Next, we focus on OCA induced by linear rules, giving a characterization of their cycle structure based on the rational canonical form of the associated Sylvester matrix. Finally, we devise an algorithm to enumerate all linear OCA pairs characterized by a single maximal cycle, and apply it up to diameter

d = 16

and

d = 13

for OCA respectively over the binary and ternary alphabets.

Has companion code repository: https://github.com/rymoah/hip-to-be-latin-square

This page was built for publication: Enumeration of Maximal Cycles Generated by Orthogonal Cellular Automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6392876)