论文标题
正交细胞自动机产生的最大周期的枚举
Enumeration of Maximal Cycles Generated by Orthogonal Cellular Automata
论文作者
论文摘要
蜂窝自动机（CA）是一个有趣的计算模型，用于设计伪数量生成器（PRNG），因为它们可以根据基础局部规则表现出复杂的动力学行为。然而，文献中提出的大多数基于CA的PRNG都遭受扩散较差，因为单个细胞的变化只能在单个时间步骤中在其附近传播。这可能会构成一个问题，尤其是当将这种PRNG用于加密目的时。在本文中，我们考虑了一种替代方法，可以通过\ emph {正交CA}（OCA）生成伪随机序列，以确保更好的扩散。定义相关PRNG之后，我们对OCA成对的最大循环进行直径为$ d = 8 $的最大循环进行了实证研究。接下来，我们关注线性规则引起的OCA，根据相关的Sylvester矩阵的理性规范形式对其周期结构进行表征。最后，我们设计了一种算法，以列举以单个最大周期为特征的所有线性OCA对，并将其应用于直径$ d = 16 $和$ d = 13 $，OCA分别在二进制和三元字母上。
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.
