The potential for 2d cellular autonama based PRNGS

A forum where anything goes. Introduce yourselves to other members of the forums, discuss how your name evolves when written out in the Game of Life, or just tell us how you found it. This is the forum for "non-academic" content.
Post Reply
Colonizor48
Posts: 30
Joined: October 16th, 2022, 4:45 pm

The potential for 2d cellular autonama based PRNGS

Post by Colonizor48 » October 2nd, 2023, 11:32 pm

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, p-boxes 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
bit-shift/rotate each int by some cryptograhpically secure amount
apply a p box to everything
bit-shift 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
Last edited by Colonizor48 on October 6th, 2023, 3:42 pm, edited 2 times in total.

User avatar
MEisSCAMMER
Posts: 96
Joined: September 20th, 2022, 5:12 pm
Location: Yes
Contact:

Re: The potential for 2d cellular autonama based PRNGS

Post by MEisSCAMMER » October 3rd, 2023, 4:20 pm

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

User avatar
confocaloid
Posts: 1561
Joined: February 8th, 2022, 3:15 pm

Re: The potential for 2d cellular autonama based PRNGS

Post by confocaloid » October 4th, 2023, 5:31 pm

Colonizor48 wrote:
October 2nd, 2023, 11:32 pm
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)
One specific possibility is to look for rules with very high-period, 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.

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.

Colonizor48
Posts: 30
Joined: October 16th, 2022, 4:45 pm

Re: The potential for 2d cellular autonama based PRNGS

Post by Colonizor48 » October 6th, 2023, 3:21 pm

confocaloid wrote:
October 4th, 2023, 5:31 pm
Colonizor48 wrote:
October 2nd, 2023, 11:32 pm
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)
One specific possibility is to look for rules with very high-period, 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.

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.
What are some potentially better canidates? i'll Do some searching for rules near long-life to see if there are any chaotic ones. Is there any way to automatically search for explosive rules like this though?

Post Reply