元胞自动机基础 元胞自动机（cellular automaton, CA）是最近一个比较热门的研究课题，其是物理、数学、计算机和生物等学科的交叉产物。在计算机领域中，CA 在人工智能、计算复杂性分析以及加密等多个领域中有着较大的用途。特别是在大约十年前，密码学家H. Gutowitz根据 CA 的基本原理，提出了分块加密算法CA-1.1，使得 CA 在密码学中真正的迈出了第一步，也使得越来越多的密码学家开始了对 CA 的研究。最近，我也开始对这个方面产生了浓厚的兴趣，并开始了一些学习，就先来简单的说说什么是CA 吧！ 简单的说，元胞自动机是一个空间、时间和状态上都离散的动态系统。构成CA 的基本单位成为元胞（cellular），规则的分布在元胞空间（spatial lattice）的格点上，且各自的状态随着时间按照一定的局部规则变化。也就是说，元胞的状态只能从一个有限的状态集中取值，每个时刻元胞的状态仅与其自身和邻居在上一时刻的状态有关，并且，所有的元胞在每个时刻均是同时更新的。 以上即是对 CA 的一个定性的描述，下面给出一个基于集合论的定量描述（L. Hurd 等）： 设 d 为 CA 空间的维数，k 代表元胞的状态，集合 S 表示 CA 的整体状态，r 表示元胞的邻居半径。为了简单起见，我们在d=1，即一维空间上对 CA 进行讨论。CA 的动态性可以由一个全局函数F: St→St+1 决定，并且，每个元胞的状态可以由一个局部函数 f:kt→kt+1 决定。 由于多维空间的CA 具有很强的复杂性，故目前对CA 的研究主要集中在一维和二维空间。就一维空间而言，CA 的结构显然只有可能是线性结构。在二维空间，CA 的结构可能有三角、四边或多边等构成方式。显然，结构上的差异会对其在计算机表示及其他部分特性上带来一定的差异。而 CA的邻居结构也通常包括Von. Neumann、Moore、扩展 Moore 和 Margolus 等多种形态，不同的邻居结构带来的特性和复杂度也不尽相同。 通过分析 CA 的构成及其基本规则，不难得出标准CA 的一些特征： 1、同质性：CA 内的每个元胞的变化都服从相同规则，且分布方式是相同的。 2、离散性：CA 在空间、时间、状态上都是离散分布的，并且其状态分布是有限的。 3、并行性：CA 每个元胞的更新都是同步进行的。 再来看看基于一维 CA 加密的一个简单讨论。分析CA 的基本机理，不难得出，基于一维 CA 的加密是一个典型分块密码。不妨假设该一维CA 的空间长度为N，则每轮更新均可得到一组长度为N的...
