I'll just cut to the chase. I need help finding a cellular automation that satisfies the following properties:
1 or 2 dimensional
Type 3
2 state
Given a random input, a random t value, and a random cell coordinate in closed space, there should be a 50/50 chance that a cell is alive or dead.
Not reversible easily.
Almost no discernible pattern in evolution(aka, no rule 30, with the triangle structures)
It should be as chaotic as possible.
I am thinking of using something like this that, combined with other steps such as bit shifts, xors, pboxes and other steps, to create a fast CSPRNG algorithm based on a cellular automata. The easier it is to compute, the better.
Again, the cellular automata would not be the only step,(that would likely be vulnerable to differential cryptanalysis), but it would be combined with other steps for obfuscation.
Pseudocode for 64 bit ints:
long a
transpose a to a 8x8 bool array
iterate the rule on the bool array for some constant t number of steps, saving each step.
convert each step back to an int
bitshift/rotate each int by some cryptograhpically secure amount
apply a p box to everything
bitshift again
xor it all together
repeat a few times
also apply the P box as often as possible
This implementation would not be secure, as it needs a larger and more complicated state, but it's a start.
Criteria 1, 2, 3 should be easy to meet, 6 and 5 might be impossible, and 4 would be easy to find approximately, but hard to verify with certainty.
Candidates:B2kn34ekz/S2457(found by randomly looking)(this automaton interestingly seems to be on the boundary between class 2, class 3, class 4. Slight changes to its transitions result in class 4 or 2 automata. For example, B2kn34ekz/S247 seems to be just barely class 4, with patterns that evolve chaotically at first before eventually turning to still lives, with at least 1 spaceship)
EDIT: Some other Criteria:
The rule should be omniperiodic
Only a small amount of "problematic" initial conditions should cause the CA to stabilize.
On a toridial universe of any size, there should exist a periodic initial condition, such that every possible state(or at least a good fraction) of the universe will be reached before returning(for now, just a 16x16 universe, for a 64 bit prng)
For an unbounded universe, periodic initial conditions should be dense
The potential for 2d cellular autonama based PRNGS

 Posts: 30
 Joined: October 16th, 2022, 4:45 pm
The potential for 2d cellular autonama based PRNGS
Last edited by Colonizor48 on October 6th, 2023, 3:42 pm, edited 2 times in total.
 MEisSCAMMER
 Posts: 96
 Joined: September 20th, 2022, 5:12 pm
 Location: Yes
 Contact:
Re: The potential for 2d cellular autonama based PRNGS
Just for future reference: this seems like something for the rule request thread.
THE TRILOGY HAS BEEN COMPLETED
next: quadrilogy??? Is that even a word
next: quadrilogy??? Is that even a word
 confocaloid
 Posts: 1561
 Joined: February 8th, 2022, 3:15 pm
Re: The potential for 2d cellular autonama based PRNGS
One specific possibility is to look for rules with very highperiod, compact oscillators (e.g. on a finite toroidal universe, or staying inside a small bounding box). Something like OCA:LongLife, except as chaotic as possible.Colonizor48 wrote: ↑October 2nd, 2023, 11:32 pmCandidates:B2kn34ekz/S2457(found by randomly looking)(this automaton interestingly seems to be on the boundary between class 2, class 3, class 4. Slight changes to its transitions result in class 4 or 2 automata. For example, B2kn34ekz/S247 seems to be just barely class 4, with patterns that evolve chaotically at first before eventually turning to still lives, with at least 1 spaceship)
B2kn34ekz/S2457 may or may not work as a PRNG; patterns in a torus often run for a long time, but then settle into some low period (= become easy to predict) at an unpredictable time.
Edit: I don't really know what could be good candidates  maybe someone else could suggest examples.
Last edited by confocaloid on October 6th, 2023, 5:22 pm, edited 1 time in total.
127:1 B3/S234c User:Confocal/R (incomplete table of INT rules)
Unlikely events happen.
My silence does not imply agreement, nor indifference. If I disagreed with something in the past, then please do not construe my silence as something that could change that.
Unlikely events happen.
My silence does not imply agreement, nor indifference. If I disagreed with something in the past, then please do not construe my silence as something that could change that.

 Posts: 30
 Joined: October 16th, 2022, 4:45 pm
Re: The potential for 2d cellular autonama based PRNGS
What are some potentially better canidates? i'll Do some searching for rules near longlife to see if there are any chaotic ones. Is there any way to automatically search for explosive rules like this though?confocaloid wrote: ↑October 4th, 2023, 5:31 pmOne specific possibility is to look for rules with very highperiod, compact oscillators (e.g. on a finite toroidal universe, or staying inside a small bounding box). Something like OCA:LongLife, except as chaotic as possible.Colonizor48 wrote: ↑October 2nd, 2023, 11:32 pmCandidates:B2kn34ekz/S2457(found by randomly looking)(this automaton interestingly seems to be on the boundary between class 2, class 3, class 4. Slight changes to its transitions result in class 4 or 2 automata. For example, B2kn34ekz/S247 seems to be just barely class 4, with patterns that evolve chaotically at first before eventually turning to still lives, with at least 1 spaceship)
B2kn34ekz/S2457 may or may not work as a PRNG; patterns in a torus often run for a long time, but then settle into some low period (= become easy to predict) at an unpredictable time.