Как MT19937RNG генерирует случайное число менее 32 бит?

Question

Мы знаем, что модуль random в python использует 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..., Где эти числа откуда?

И как мы все знаем, если мы получим 624 последовательных 32-битных случайных числа, сгенерированных MT19937RNG, мы можем легко восстановить начальное число и вычислить любое случайное число, но если мы можем получить только последовательные случайные числа меньше, чем 32-битный, как 1-битный, можем ли мы все еще сломать MT19937RNG?

Answer 1

выходные данные random.getrandbits(1) становятся 0,0,0,1 ..., откуда эти числа?

Это старшие биты результатов random.getrandbits(32). Просто посмотрите на источник в файле Modules/_randommodule.c

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

, если мы можем получить только последовательные случайные числа меньше 32-битных, как 1-битные, можем ли мы все еще ломать MT19937RNG?

Да. Конечно, нам нужно в 32 раза больше значений. По сути, мы берем 19937 бит состояния как неизвестные, записываем одно линейное уравнение этих переменных для каждого известного нам бита и решаем.