Search for reverse surgery for George Marsaglia XorShift RNG

Question

annotation

Hello, suppose you have a 128-bit machines (represented by four 32-bit words X, Y, Z, W), which changes its state according to the following rule:

X = ...
Y = ...
Z = ...
W = ...

void next()
{
    var t = X ^ (X << 11);

    X = Y;
    Y = Z;
    Z = W;

    W = W ^ (W >> 19) ^ (t ^ (t >> 8));
}

^ - indicates a binary operation XOR

<< - indicates a double left shift operation

>> - denotys binary shift operation on the right side

It is guaranteed that the above automata do not generate any collisions, i.e. each state is the result of one (and only one) previous state. It is also guaranteed that the aforementioned state machine creates 2 ^ 128 unique states.

Question

(X,Y,Z,W) next (.. prev), .

, (X=1, Y=2, Z=3, W=4) next, (X=2, Y=3, Z=4, W=2061), , prev (X=1, Y=2, Z=3, W=4).

P.S.

next XorShift,

https://en.wikipedia.org/wiki/Xorshift

, Guid.Next(...), Guid.Prev(...)

---

Niklas B. #, , , - Random.Next() Random.Prev():

public class Xor128
{
    public UInt32 X { get; set; }
    public UInt32 Y { get; set; }
    public UInt32 Z { get; set; }
    public UInt32 W { get; set; }

    public Xor128()
    {

    }

    public Xor128(UInt32 x, UInt32 y, UInt32 z, UInt32 w)
    {
        X = x;
        Y = y;
        Z = z;
        W = w;
    }

    //private UInt32 UnXorShl(UInt32 x, Int32 shift)
    //{
    //    for (var i = shift; i < 32; i <<= 1) {
    //        x ^= x << i;
    //    }

    //    return x;
    //}

    //private UInt32 UnXorShr(UInt32 x, Int32 shift)
    //{
    //    for (var i = shift; i < 32; i <<= 1) {
    //        x ^= x >> i;
    //    }

    //    return x;
    //}

    //public UInt32 Prev()
    //{
    //    var t = UnXorShr(W ^ Z ^ (Z >> 19), 8);

    //    W = Z;
    //    Z = Y;
    //    Y = X;
    //    X = UnXorShl(t, 11);

    //    return W;
    //}

    public UInt32 Prev()
    {
        var t = W ^ Z ^ (Z >> 19);

        t ^= t >> 8;
        t ^= t >> 16;

        W = Z;
        Z = Y;
        Y = X;

        t ^= t << 11;
        t ^= t << 22;

        X = t;

        return W;
    }


    public UInt32 Curr()
    {
        return W;
    }

    public UInt32 Next()
    {
        UInt32 t = X ^ (X << 11);

        X = Y;
        Y = Z;
        Z = W;

        return W = W ^ (W >> 19) ^ (t ^ (t >> 8));
    }
}

. :

public class Xor128 {
    public var X: UInt32
    public var Y: UInt32
    public var Z: UInt32
    public var W: UInt32

    public convenience init(uuid: uuid_t) {
        let xa = (UInt32(uuid.0 ) << 24)
        let xb = (UInt32(uuid.1 ) << 16)
        let xc = (UInt32(uuid.2 ) << 8 )
        let xd = (UInt32(uuid.3 ) << 0 )

        let ya = (UInt32(uuid.4 ) << 24)
        let yb = (UInt32(uuid.5 ) << 16)
        let yc = (UInt32(uuid.6 ) << 8 )
        let yd = (UInt32(uuid.7 ) << 0 )

        let za = (UInt32(uuid.8 ) << 24)
        let zb = (UInt32(uuid.9 ) << 16)
        let zc = (UInt32(uuid.10) << 8 )
        let zd = (UInt32(uuid.11) << 0 )

        let wa = (UInt32(uuid.12) << 24)
        let wb = (UInt32(uuid.13) << 16)
        let wc = (UInt32(uuid.14) << 8 )
        let wd = (UInt32(uuid.15) << 0)

        self.init(
            x: xa + xb + xc + xd,
            y: ya + yb + yc + yd,
            z: za + zb + zc + zd,
            w: wa + wb + wc + wd
        )
    }

    public convenience init(uuid: UUID) {
        self.init(uuid: uuid.uuid)
    }

    public init(x: UInt32, y: UInt32, z: uint32, w: UInt32) {
        X = x
        Y = y
        Z = z
        W = w
    }

    @discardableResult
    public func next() -> UInt32 {
        let t = X ^ (X << 11);

        X = Y;
        Y = Z;
        Z = W;

        W = W ^ (W >> 19) ^ (t ^ (t >> 8))

        return W;
    }

    public var curr: UInt32 {
        return W
    }

    @discardableResult
    public func prev() -> UInt32 {
        var t = W ^ Z ^ (Z >> 19);

        t ^= t >> 8;
        t ^= t >> 16;

        W = Z;
        Z = Y;
        Y = X;

        t ^= t << 11;
        t ^= t << 22;

        X = t;

        return W;
    }
}

Answer 1

- XOR f(x) = x ^ (x << s) s > 0. f (x), s x .

, , XORed, f (x). Python:

def reverse_xor_lshift(y, shift, w=32):
    x = y & ((1<<shift) - 1)
    for i in range(w - shift):
        x |= (1 if bool(x & (1<<i)) ^ bool(y & (1<<(shift+i))) else 0)<<(shift+i)
    return x

. , :

def reverse_bin(x, w=32):
    return int(bin(x)[2:].rjust(w, '0')[::-1], 2)

def reverse_xor_rshift(y, shift, w=32):
    # for simplicity, we just reuse reverse_xor_lshift here
    return reverse_bin(reverse_xor_lshift(reverse_bin(y), shift))

def forward(X, Y, Z, W):
    t = (X ^ (X << 11)) & 0xffffffff
    X = Y
    Y = Z
    Z = W
    W = W ^ (W >> 19) ^ (t ^ (t >> 8))
    return (X, Y, Z, W)

def backward(X, Y, Z, W):
    t = reverse_xor_rshift(W ^ Z ^ (Z >> 19), 8)
    return (reverse_xor_lshift(t, 11), X, Y, Z)

backward - , . :

import random
for _ in range(1000):
    X, Y, Z, W = [random.randint(0,2**32-1) for _ in range(4)]
    assert backward(*forward(X,Y,Z,W)) == (X, Y, Z, W)

, .

Answer 2

Y, Z W . X :

W' = W ^ (W >> 19) ^ (t ^ (t >> 8)), -> t ^ (t >> 8) = W' ^ (W ^ (W >> 19))

, t ^ (t >> 8) = W' ^ (W ^ (W >> 19)) = a

t = X ^ (X << 11) 

-> t ^ (t >> 8) = X ^ (X << 11) ^ ((X ^ (X <<11)) >> 8) 
                = X ^ (X << 11) ^ (X >> 8) ^ (X << 3)

X x0, x1, x2,... x31 a a0, a1,..., :

x0 ^ x8 = a0
x1 ^ x9 = a1
.....

, :

(x0 + x8) % 2 = a0
(x1 + x9) % 2 = a1
....

, .