如何在 Python 的随机性限制下创造一个真正不可能的条件？

Question

所以我试图找到一种方法来获得基于随机生成的极不可能的条件。为了更好地解释，这里有一个例子：

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

由于 mersene twister 的限制和功能及其数字分布的均匀性，我们很可能会在两个列表中生成 1000 万个数字，其中当顺序无关紧要并删除重复项时，它们会经常匹配。

这种情况并不少见，但下面的代码稍微好一点：

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 中的随机性来编写一个条件，这种情况真的极不可能发生？..也就是说，需要一年或更长时间才能破解。

或者我想转向哈希匹配...创建随机 SHA256 哈希，然后生成随机大数据，并通过 sha256 对其进行哈希处理以尝试匹配哈希。但是我不知道在那种情况下观察概率的方法。

Answer 1

您可能对 几何分布 感兴趣，它计算第一次成功之前的失败次数（有些作品说它计算的是失败次数加上第一次成功）。例如，连续不失败的概率是 1/2，连续一次失败的概率是 1/4，连续两次失败的概率是 1/8，连续三次失败的概率是 1/16，依此类推。如果我们用一个零位表示失败，一个位表示成功，这意味着随着更多的零位，随机生成那么多零位的可能性就会降低。作为 "improbable event" 的示例，您可以将连续 30 个或更多零位视为不可能。

Mersenne Twister 和伪随机数生成器 (PRNG) 通常具有循环。此循环的大小会影响 PRNG 可以连续生成多少个零位。例如，Mersenne Twister 有一个 2^19937 - 1 个数字的循环，因此理论上它可以循环遍历除全零状态之外的所有状态。因此，它可以连续生成不超过 19937 * 2 个零位。（这是如果我们将 Mersenne Twister 视为一次输出单个位，而不是 32 位。）

这与 nondeterministic random number generators (RNG) 形成对比，后者没有循环但仍会生成随机行为的数字。如果它产生的数是独立的、统一的、随机的比特，那么RNG最多能随机产生多少个零比特就不知道了。在 Python 的 secrets 模块中可以找到使用非确定性的 RNG 的一个示例，特别是 secrets.randbelow()。（实际上，这个模块很可能使用 PRNG，但可能会不时地从不确定的来源收集 "entropy"，因此实际上模块的 RNG 是不确定的。）

如何在 Python 的随机性限制下创造一个真正不可能的条件？

How to make a truly improbable condition with limitations of Python's random?

python

random

probability

mersenne-twister