随机算法设计中的随机发电机注意事项

Question

众所周知，随机算法（至少在BPP和RP中的算法）的效率取决于所使用的随机发生器的质量。在实践中，不可用的完美随机来源。虽然证明所有$ 0 < delta leq frac {1} {2} $ the Identities bpp = $ delta $ -bpp和rp = $ delta $ -rp Hold，但原始的是不正确的用于县长随机源的算法也可以直接用于$ delta $ -random源。相反，必须进行一些模拟。该模拟是多项式的，但是所得算法的效率不如原始算法。

此外，就我所知，实践中使用的随机发电机通常不是$ delta $ - 源，而是伪随机来源，在最坏情况下可能会表现出极糟糕的情况。

根据 维基百科:

在通常的实践中，使用伪数量生成器代替真实的随机位来近似随机算法。这样的实现可能会偏离预期的理论行为。

实际上，我现在已经看到的随机算法的实现仅仅是使用伪源来源运行的算法实现的实现。

我的问题是，是否有这种共同做法的理由。是否有任何理由期望在大多数情况下，算法将返回正确的结果（具有BPP REP中的概率）？ Wikipedia引用中提到的“近似”如何被形式化？至少在预期的情况下，可以以某种方式估计提到的偏差吗？是否可以说，在完美的随机源上运行的蒙特卡洛随机算法会在伪源源运行时会变成良好的随机算法？还是还有其他类似的考虑？

Answer 1

这是一个很好的理由。假设您使用加密强度伪数字生成器来生成某些随机算法所需的随机位。然后，只要加密算法是安全的，则所得算法将继续起作用。

一个 加密强度伪数编号生成器 是密码学的标准工具，它接受短种子（例如128位真实的随机性），并生成无限数量的伪随机位。它具有非常强大的安全保证：只要基本的加密原始词没有破坏，那么伪随机位将与任何可行的过程完全无法区分与真正的随机位完全不同（尤其是，尤其没有有效的算法可以区分其输出的输出来自一系列真实的随机位）。例如，我们可能会得到保证，说明：如果保理很难（或者，如果RSA安全；或者，如果AES安全），那么这是一个很好的伪随机生成器。

这确实是一个非常有力的保证，因为普遍认为它很难打破这些加密原语。例如，如果您可以找出一种有效的方法来考虑非常大的数字，那么这将是一个突破性的结果。出于所有实际目的，您可以表现得好像加密原语是坚不可摧的。这意味着，出于所有实际目的，您可以像加密强度的伪数字生成器的输出一样，基本上与一系列真实随机位相同。特别是，这是随机算法所需的随机性的良好来源。

（我已经掩盖了这样一个事实，即要使用加密强度prng，您仍然需要独自找到128位真正的随机性才能形成种子。但是通常这并不难，确实有加密工具也协助完成这项任务。）

在实践中，变得非常好的伪随机位与

$ cat /dev/urandom

Answer 2

众所周知，随机算法（至少在BPP和RP中的算法）的效率取决于所使用的随机发生器的质量。 我必须不同意。与trully随机序列相比，算法的性能从集合中运行一个随机序列，可以保证该算法的性能，这是一个很好的伪随机序列合奏。如果您没有这样的保证，则无法得出结论，该算法会效果不佳 - 您只是不知道。

这种常见做法是否有理由？ 有用。

是否可以说，在完美的随机源上运行的蒙特卡洛随机算法会在伪源源运行时会变成良好的随机算法？ 复杂性理论遭受了两个缺点。第一个是很难证明任何东西（例如，P与NP开放）。第二个是它主要与最坏情况分析有关。组合在一起，这两个局限性排除了复杂性理论是实践中算法行为的良好模型。