Xorshift32の逆算
Xorshift32は以下のようなアルゴリズム。
code:Ruby
def xorshift32(x)
x ^= x << 13 & 0xffffffff
x ^= x >> 17
x ^= x << 5 & 0xffffffff
x
end
この演算は可逆なので、ひとつ前の値を求めることができる。
ビット演算による方法
具体的には、以下のようにする。
code:Ruby
def xorshift32_reverse(y)
# x ^= x << 5 & 0xffffffff の逆
# LSB から順に、 5 ビットずつ求める
x = y & 0x0000001f
x = y ^ (x << 5) & 0x000003ff
x = y ^ (x << 5) & 0x00007fff
x = y ^ (x << 5) & 0x000fffff
x = y ^ (x << 5) & 0x01ffffff
x = y ^ (x << 5) & 0x3fffffff
x = y ^ (x << 5) & 0xffffffff
y = x
# x ^= x >> 17 の逆
# MSB から順に、 15 ビットずつ求める
x = y & 0xfffe0000
x = y ^ x >> 17 & 0xfffffffc
x = y ^ x >> 17 & 0xffffffff
y = x
# x ^= x << 13 & 0xffffffff の逆
# LSB から順に、 13 ビットずつ求める
x = y & 0x00001fff
x = y ^ (x << 13) & 0x03ffffff
x = y ^ (x << 13) & 0xffffffff
x
end
Xorshift64, 128でも同様の方法で求めることができる。
行列累乗による方法
進める操作は$ F_2上の行列として表すことができる。
Xorshift32の周期は$ 2^{32}-1であるため、行列累乗で$ 2^{32}-2回進めるとひとつ前の値を求めることができる。
code:Rust
fn main() {
let seed = 0x12345678_u32;
println!("{:#032x}", xorshift32(seed, (1 << 32) - 2));
}
fn xorshift32(seed: u32, iteration: usize) -> u32 {
fn odd_ones(mut x: u32) -> u32 {
x ^= x >> 16;
x ^= x >> 8;
x ^= x >> 4;
x ^= x >> 2;
x ^= x >> 1;
x & 1
}
for i in 0 .. 32 {
}
matrix
}
fn left_xorshifted(k: usize) -> u32; 32 { let mut matrix = identity();
for i in k .. 32 {
}
matrix
}
fn right_xorshifted(k: usize) -> u32; 32 { let mut matrix = identity();
for i in k .. 32 {
}
matrix
}
for k in 0 .. 32 {
for j in 0 .. 32 {
btj |= (bk >> j & 1) << k; }
}
for i in 0 .. 32 {
for j in 0 .. 32 {
ci ^= odd_ones(ai & btj) << j; }
}
c
}
let mut r = identity();
while n != 0 {
if n & 1 != 0 {
r = multiply(&r, &a);
}
a = multiply(&a, &a);
n >>= 1;
}
r
}
let mut matrix = identity();
matrix = multiply(&left_xorshifted(13), &matrix);
matrix = multiply(&right_xorshifted(17), &matrix);
matrix = multiply(&left_xorshifted(5), &matrix);
matrix = power(matrix, iteration);
let mut value = 0u32;
for bit in 0 .. 32 {
value |= odd_ones(matrixbit & seed) << bit; }
value
}