💻 computer science

Cellular Automata based Resource Efficient Maximally Equidistributed Pseudo-Random Number Generators

This paper proposes and validates a family of lightweight, combined linear cellular automaton-based pseudo-random number generators that overcome the equidistribution weaknesses of existing CA-PRNGs by achieving maximal period, maximal equidistribution, and performance comparable to the Mersenne Twister.

Original authors: Bhuvaneswari A, Kamalika Bhattacharjee

Published 2026-03-23

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Bhuvaneswari A, Kamalika Bhattacharjee

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are running a massive casino. To keep things fair, you need a machine that spits out numbers that look completely random, like rolling dice that have never been touched before. In the world of computers, these machines are called Pseudo-Random Number Generators (PRNGs).

The problem is, computers are actually very predictable. They follow strict rules. So, making them act "random" is a huge challenge. If the numbers aren't truly random, the casino loses money, or a secret code gets cracked.

This paper is about building a better, faster, and more efficient "dice machine" using a concept called Cellular Automata.

Here is the story of how the authors fixed the broken machines, explained simply:

1. The Problem: The "Boring" Dice

The authors looked at the existing machines (called Linear Cellular Automata). They found a major flaw: Equidistribution.

The Analogy: Imagine you have a giant grid of 100 squares. You want to drop marbles into these squares so that every single square gets exactly the same number of marbles over time.
The Flaw: The old machines were like a clumsy kid throwing marbles. They would accidentally drop 50 marbles in the top-left corner and leave the bottom-right corner empty. Even though the total number of marbles was huge, they weren't spread out evenly. In math terms, they failed the "Equidistribution" test. They were predictable in subtle ways.

2. The Solution: The "Two-Headed" Machine

To fix this, the authors decided to combine two machines instead of using one.

The Analogy: Imagine you have two dice rollers. One is a bit lazy, and the other is a bit jittery. If you ask them to roll at the same time and add their results together, the laziness of one cancels out the jitteriness of the other.
The Method: They took two "Maximal Length" Cellular Automata (which are just very long, complex rule-based patterns) and mashed them together using a simple math trick called XOR (think of it as a "switch" that flips bits if they are different).

3. The Secret Sauce: The "Skip" (Time Spacing)

Here is where the magic happened. Even after combining two machines, they still had a problem. Because these machines follow simple rules, they tend to create beautiful, repeating patterns—like a Sierpinski Triangle (a fractal triangle shape).

The Analogy: Imagine two dancers moving in perfect sync. If you watch them, you see a beautiful, predictable pattern. It's not random; it's choreography.
The Fix: The authors introduced Time Spacing. Instead of watching the dancers every second, they told the computer to skip a few seconds between observations.
- Skip 1 second: You still see the pattern.
- Skip 5 seconds: The pattern breaks. The dancers look like they are moving chaotically.
- Skip 7 or 8 seconds: The pattern completely vanishes. The movement looks like pure noise.

By skipping steps (specifically between 2 and 10 steps), they shattered the predictable patterns, turning the "choreographed dance" into a chaotic, unpredictable mess. This is what they call Maximal Equidistribution.

4. Why This Matters: Light-Weight and Fast

The authors didn't just want a random machine; they wanted a light-weight one.

The Analogy: Most high-quality random number generators are like a massive, fuel-hungry truck. They work great, but they need a lot of power and memory. The authors wanted to build a scooter.
The Result: Their new machine uses very little computer memory (it fits easily on small chips or in phones) but performs just as well as the giant trucks.
- They tested their "scooter" against the industry giant, the Mersenne Twister (the current gold standard).
- The Score: Their new machine was faster than the Mersenne Twister and passed almost every statistical test for randomness.

Summary of the Breakthrough

Old Machines: Fast and small, but the numbers weren't spread out evenly (bad randomness).
New Idea: Combine two small machines.
The Twist: Don't look at the result every time; skip a few steps in between (Time Spacing).
The Result: A machine that is small, fast, and produces numbers that are perfectly spread out and impossible to predict.

In a nutshell: The authors took simple, predictable patterns, smashed two of them together, and then looked at the result through a "skip-a-beat" filter. The result was a random number generator that is small enough for a smartwatch but powerful enough to secure the internet.

1. Problem Statement

The paper addresses the limitations of existing Linear Pseudo-Random Number Generators (PRNGs), particularly those based on Cellular Automata (CA) and Linear Feedback Shift Registers (LFSRs).

Equidistribution Deficit: While existing linear CA-based PRNGs are resource-efficient and have long periods, they fail to satisfy the maximal equidistribution property. This theoretical quality metric measures the uniformity of generated numbers across all possible dimensions. Existing CA-PRNGs often exhibit self-similar patterns (e.g., Sierpinski triangles) due to their chaotic nature, leading to poor statistical randomness in high dimensions.
Trade-off in Current Solutions:
- Tempering: Using output transformation functions (tempering) to fix equidistribution increases computational overhead and hardware complexity, violating the "light-weight" requirement.
- Combined Generators: Simply combining multiple CAs via XOR often fails to achieve maximal equidistribution if the component periods are not carefully managed or if the underlying structure retains symmetry.
- Light-weight Constraints: Modern applications (FPGA, embedded systems, multicore CPUs) require PRNGs that fit within standard word sizes (32–128 bits) and minimize resource usage, yet current lightweight CA-PRNGs often fail statistical testbeds.

2. Methodology

The authors propose a novel framework for designing Light-weight Combined CA-based PRNGs that achieve maximal equidistribution without complex tempering functions.

A. Component Selection

The authors utilize Linear Maximal Length Cellular Automata (specifically Elementary Cellular Automata using rules 90 and 150).

Sources: They select components from two established sources (Ref [4] and Ref [7]) where the rule vectors are highly uniform (mostly Rule 90 or Rule 150, with only 1 or 2 exceptions). This ensures hardware efficiency.
Constraints: Component sizes ( $k$ ) are restricted to $32 \le k \le 128$ bits to fit computer word sizes. The number of components is limited to two to maintain simplicity.
Chaos Verification: The authors verify that these specific CA configurations are chaotic (using the P-parameter) to ensure they are suitable sources of randomness.

B. The Combined Generator with Time Spacing

To break the self-similar patterns inherent in chaotic CAs and achieve maximal equidistribution, the authors introduce Time Spacing ( $s$ ):

Combination: Two maximal length CAs ( $CA_1, CA_2$ ) with relatively prime periods are initialized.
Skipping: Instead of combining the state at every time step, the generators evolve for $s$ steps, and the outputs are combined (via XOR) only at the $s$ -th step.
Mathematical Basis: The combined sequence is derived from the matrix $A = T^s$ , where $T$ is the characteristic matrix of the CA. If $\gcd(s, \rho) = 1$ (where $\rho$ is the period), the combined generator achieves a period close to maximal ( $LCM(\rho_1, \rho_2) \approx 2^{k_1+k_2}$ ).
Optimization: The authors restrict $s$ to the range $2 \le s \le 10$ to balance randomness quality with computational speed (keeping the generator light-weight).

C. Evaluation Criteria

Theoretical: Verification of Maximal Equidistribution (ME) using the resolution gap ( $\Lambda_t$ ) and rank checks of binary matrices (Propositions 2, 3, and 4).
Empirical: Testing against standard statistical testbeds: Dieharder, SmallCrush, and BigCrush (TestU01 suite).
Visual: Analysis via Space-Time Diagrams to observe the disappearance of self-similar patterns.
Performance: Speed comparison (CPU time) against Mersenne Twister, Tausworthe, and WELL generators.

3. Key Contributions

Identification of Weakness: The paper demonstrates that existing linear CA-based PRNGs (even those with maximal periods) fail the maximal equidistribution test, making them theoretically suboptimal for high-dimensional applications.
Time-Spacing Mechanism: The introduction of time spacing ( $s$ ) as a lightweight method to break chaotic self-similarity and achieve maximal equidistribution without external tempering functions.
Comprehensive Search: The authors systematically evaluated thousands of combinations of CA sizes ( $32 \le k \le 128$ $32 \leq k \leq 128$ ) and time spacing values ( $2 \le s \le 10$ $2 \leq s \leq 10$ ).
- They identified 368 specific combinations that achieve maximal equidistribution.
- Among these, they isolated generators that also pass the majority of empirical statistical tests.
Resource Efficiency: The proposed generators are designed to be hardware-friendly, utilizing simple XOR gates and minimal rule variations, making them ideal for FPGA and embedded implementations.

4. Results

Theoretical Quality: The proposed combined PRNGs with time spacing successfully achieve Maximal Equidistribution (ME), a property previously unattained by simple linear CA-PRNGs.
Statistical Performance:
- Many proposed generators (e.g., combinations like $(31, 32, s=7/8)$ , $(47, 72, s=10)$ ) passed all or the majority of tests in Dieharder, SmallCrush, and BigCrush.
- Some combinations that achieved ME but had periods slightly reduced by the time spacing factor still passed all tests.
Visual Verification: Space-time diagrams confirmed that time spacing effectively destroys the self-similar patterns (like Sierpinski triangles) seen in standard CA evolution, resulting in "noisy" and random-looking patterns.
Performance Comparison:
- Speed: The proposed PRNGs are faster than the Mersenne Twister but slightly slower than non-time-spaced generators (like standard Tausworthe or GFSR4) due to the skipping steps.
- Trade-off: Despite the slight speed penalty compared to the fastest linear generators, they offer superior equidistribution and statistical robustness compared to Mersenne Twister (which is not maximally equidistributed).

5. Significance

This work bridges the gap between hardware efficiency and theoretical randomness quality.

Practical Application: It provides a blueprint for designing PRNGs suitable for resource-constrained environments (FPGAs, IoT devices) that do not compromise on cryptographic or simulation-grade randomness.
Theoretical Advancement: It proves that maximal equidistribution can be achieved in linear systems through structural modifications (time spacing) rather than complex output transformations.
Future Impact: The identified parameter sets (specific $k_1, k_2, s$ combinations) serve as a ready-to-use library for developers needing high-quality, lightweight random number generation. The authors suggest future work could focus on optimizing the time spacing mechanism to further reduce computational overhead while maintaining these high quality metrics.