python - MT19937RNG如何生成小于32位的随机数？

Question

我们知道python中的random模块使用MT19937来生成32位随机数，例如:

>>> import random
>>> random.seed(123)
>>> random.getrandbits(32)
224899942L
>>> random.getrandbits(32)
1149664691L
>>> random.getrandbits(32)
374463918L
>>> random.getrandbits(32)
3302642556L

当我设置相同的种子时，输出与 MT19937 的输出相同。

但是，如果我想生成一个小于32位的随机数，比如我想用random.getrandbits(1)生成一个1位的随机数，一开始我以为结果只是random.getrandbits(32)&1，但是当我付诸实践时，发现并非如此:

>>> import random
>>> random.seed(123)
>>> random.getrandbits(1)
0L
>>> random.getrandbits(1)
0L
>>> random.getrandbits(1)
0L
>>> random.getrandbits(1)
1L

现在我不知道为什么输出会变成0,0,0,1...，这些数字是从哪里来的？

众所周知，如果我们得到 MT19937RNG 生成的 624 个连续 32 位随机数，我们可以轻松恢复种子并计算任意随机数，但如果我们只能得到小于 32 位的连续随机数，例如1位，我们还能破解MT19937RNG吗？

Answer 1

the output of random.getrandbits(1) become 0,0,0,1..., Where do these numbers come from?

这些是random.getrandbits(32)结果的高位。只要看看source在文件 Modules/_randommodule.c

if (k <= 32)  /* Fast path */
    return PyLong_FromUnsignedLong(genrand_int32(self) >> (32 - k));

if we can only get consecutive random numbers less than 32-bit like 1-bit, can we still break the MT19937RNG?

是的。当然，我们需要 32 倍以上的值。基本上，我们将状态的 19937 位作为未知数，为我们已知的每一位写出这些变量的线性方程，然后求解。