Как сделать действительно невероятное условие с ограничениями случайных чисел Python? - PullRequest
0 голосов
/ 09 апреля 2020

Поэтому я пытаюсь найти способ получить невероятно невероятное состояние, основанное на случайных поколениях. Чтобы лучше объяснить, вот пример:

from random import *
import ctypes

random1 = [randint(0, 2 ** 32 - 1) for j in range(10000000)]

while True:
    random2 = [randint(0, 2 ** 32 - 1) for i in range(10000000)]
    if set(random2) == set(random1):
        MessageBox = ctypes.windll.user32.MessageBoxW
        MessageBox(None, 'Match', 'Output', 0)
        break

Из-за ограничений и функциональности мерсена твистера и равномерности его распределения чисел, вполне вероятно, что мы сгенерируем 10 миллионов номеров в обоих списках, где когда порядок не имеет значения и дубликаты удаляются, они будут совпадать довольно часто.

Это не так уж редко, но следующий код немного лучше:

from random import *
import ctypes

while True:
    if random() == 0.0:
        MessageBox = ctypes.windll.user32.MessageBoxW
        MessageBox(None, 'Match', 'Output', 0)
        break

Это много Это случается реже, но при большой производительности в одноядерном процессоре, которая сегодня довольно распространена, вероятность того, что победа будет достигнута через 1 день, все еще велика. Вероятность составляет 1/2 ^ 56, и с учетом ограничений твистера Мерсенна, это не так уж вероятно.

Есть ли хороший способ написать условие, использующее случайность в python, которое действительно быть крайне маловероятным, чтобы это произошло? .. То есть, для взлома понадобится год или больше.

В качестве альтернативы я решил обратиться к совпадению ha sh, создавая случайный SHA256 га sh, затем генерирует случайные большие данные и хэширует их через sha256, чтобы попытаться найти соответствие ha sh. Но я не знаю, как наблюдать вероятность в этом случае.

1 Ответ

1 голос
/ 09 апреля 2020

Возможно, вас заинтересует распределение geometryri c , в котором подсчитывается количество отказов до первого успеха (в некоторых работах указывается, что это число плюс первый успех). Например, вероятность отсутствия ошибок в строке равна 1/2, одна ошибка в строке - 1/4, две строки - 1/8, три в строке - 1/16 и т. Д. Если мы возьмем нулевой бит для обозначения сбоя и один бит для значимости успеха, это означает, что при большем количестве нулевых битов становится менее вероятным, что такое количество нулевых битов будет генерироваться случайным образом. В качестве примера «невероятного события» вы можете рассматривать 30 или более нулевых битов подряд как невероятные.

Генераторы Мерсенна Твистера и псевдослучайных чисел (PRNG) в целом имеют циклы. Размер этого цикла влияет на количество нулевых битов, которые PRNG может сгенерировать подряд. Например, Mersenne Twister имеет цикл 2 ^ 19937 - 1 число, так что теоретически он может циклически проходить через все состояния, кроме состояния со всеми нулями. Таким образом, он может генерировать не более 19937 * 2 нулевых битов подряд. (Это если мы рассматриваем Mersenne Twister как вывод отдельных битов, а не 32 битов одновременно).

Это в отличие от недетерминированных c генераторов случайных чисел (RNG), которые не имеют циклов, но все еще генерируют числа со случайным поведением. Если числа, которые он генерирует, являются независимыми, единообразными и случайными битами, тогда не известно, сколько нулевых битов RNG может генерировать случайным образом максимум. Один пример ГСЧ, который использует недетерминизм, находится в модуле Python secrets, в частности secrets.randbelow(). (На практике этот модуль, вероятно, будет использовать PRNG, но может время от времени собирать «энтропию» из недетерминированных c источников, так что на практике RNG модуля является недетерминированным c.)

...