均匀分布性(equidistribution)是一种理论质量指标,用于衡量线性伪随机数生成器(PRNG)的输出均匀性。本文首先指出,所有现有基于线性元胞自动机(CA)的伪随机数生成器在均匀分布性方面均表现较弱。随后,我们提出一系列轻量级组合式CA-based PRNG,采用时间间隔为 $2 \leq s \leq 10$ 的设计,并基于阶数为 $31 \leq k \leq 128$(接近计算机字长)的线性最大长度元胞自动机。我们证明,这些PRNG不仅达到最大周期,而且满足极大均匀分布性(maximal equidistribution property)。最后,我们验证这些组合式最大长度CA-based PRNG几乎通过全部经验测试套件,其运行速度与性能与梅森旋转算法(Mersenne Twister)相当。
An equidistribution is a theoretical quality criteria that measures the uniformity of a linear pseudo-random number generator (PRNG). In this work, we first show that all existing linear cellular automaton (CA) based pseudo-random number generators (PRNGs) are weak in the equidistribution characteristic. Then we propose a list of light-weight combined CA-based PRNGs with time spacing ($2 \leq s \leq 10$) using linear maximal length cellular automata of degree $31 \leq k \leq 128$ (close to computer word size). We show that these PRNGs achieve maximal period as well as satisfy the maximal equidistribution property. Finally, we show that these combined maximal length CA-based PRNGs pass almost all the empirical testbeds, with speed and performance comparable to the Mersenne Twister.