Re: BitBox PRNG

From: J. Campbell (mango_maniac_at_yahoo.com)
Date: 08/30/03 

Date: 30 Aug 2003 04:44:58 -0700

Michael Amling <nospam@nospam.com> wrote in message news:<2OV3b.17100$
> > the mixing scheme I used is the oft-maligned rule30 1-D automata using
> > cyclic boundary conditions.
>
> Does a rule30 1-D automaton admit of a brief description of its
> effect on either abcd efgh ijkl mnop or aeim bfjn cgko dhlp?
>
> --Mike Amling

Mike, The rule 30Automata Wolfram's nomenclature for a
nearest-neighbor 1D automata. Rule30 is as follows (top line is the
neighborhood at tn, bottom line is state of center block at tn+1).

111 110 101 100 011 010 001 000
 0 0 0 1 1 1 1 0

This is called Rule 30 because 00011110 is binary 30. There are 256
possible such nearest neighbor automata, and rule 30 and rule 45 can
both be used as PRNGs. Anyway...back to Rule30...it is equivalent to
"make the center block on the next line equal to the center block ORed
against the right block, and the result of the operation XORed against
the left block".

It's important to update the whole automata at once or else it's
trivial to go backwards.

Anyway...this automata is one-way, because it loses information about
the blocks that are ORed together at each step. It is possible to
calculate possible predecessor states, but this calculation becomes
daunting as the size of the automata increases, and as the number of
not-known lines/number of steps between known states of the system
increases.

so...to answer you question considering a 4-element automata,
abcd --> a'b'c'd' using wrapping boundary conditions

where:
a' = d XOR (a OR b)
b' = a XOR (b OR c)
c' = b XOR (c OR d)
d' = c XOR (d or a)

and similarly,
aeim --> a'e'i'm' using wrapping boundary conditions

where
a' = m XOR (a OR e)
e' = a XOR (e OR i)
i' = e XOR (i OR m)
m' = i XOR (m OR a)

Joe