随机素数和 Rabin Karp 子串搜索

Question

我正在阅读 Sedgewick 的 Rabin-Karb 算法。书上说：

We use a random prime Q taking as large a value as possible while avoiding overflow

初读时我没有注意到 random 的重要性，当我看到代码中使用了 long 时，我的第一个想法是：
a) 使用 Eratosthene 的筛子找到适合 long
的大素数 或
b) 从素数列表中查找任何足够大且大于 int 的素数，并将其用作常数。

但是接下来的解释是：

We will use a long value greater than 10^20 making the probability that a collision happens less than 10^-20

这部分让我感到困惑，因为 long 不适合 10^20，更不用说比它更大的值了。 然后当我检查素数的计算时，这本书推迟到一个只有以下提示的练习：

A random n-digit number is prime with probability proportional to 1/n

这是什么意思？

所以基本上我没有得到的是：
a) 使用 random 素数是什么意思？为什么我们不能预先计算它并将其用作常数？
b) 为什么提到 10^20 因为它超出了 long 的范围？
c) 该提示有何帮助？具体是什么意思？

Answer 1

，Sedgewick 试图简化算法，但在细节上略有错误。首先，如您所见，10²⁰ 不能用 64 位表示。然而，即使采用接近 2⁶³ − 1 的质数，您也可能需要一些空间来按正常方式乘法而不溢出，以便后续的 modulo 是正确的.答案使用 31 位质数，这使得这很容易，但仅提供 10⁻⁹ 范围内的碰撞概率。

原始版本使用 Rabin fingerprints and a random irreducible polynomial 而不是 ₂[x]，从代数数论的角度来看，它的行为很像整数上的随机素数。如果我们选择多项式的次数为32次或64次，那么指纹完全适合一个适当长度的计算机字，而且多项式加法和减法都是按位异或，所以不会溢出。

现在，Sedgewick 可能不想解释多项式环的工作原理。美好的。如果我必须在实践中实施这种方法，我会选择一个接近最大值 的素数 p，这很容易 mod 通过廉价的指令 （我偏向于2³¹ − 2²⁷ + 1；实际编辑 2³¹ − 1 效果更好，因为我们在这里不需要平滑素数），然后在 [1, p−1] 中选择一个随机数来评估多项式（维基百科是这样解释的）。我们需要一些随机性的原因是，否则不经意的对手可能会选择一个保证有很多哈希冲突的输入，这会严重降低 运行 时间。

Sedgewick 想要更接近原版，然而，它本质上是在 x 的固定值（在使用多项式环的原始版本中字面意思为 x）处计算多项式。他需要一个随机素数，这样不经意的对手就无法设计碰撞。筛选足够大的数字是非常低效的，所以他求助于素数定理（这是他暗示背后的数学原理，但它仅渐近成立，这在理论上造成了很大的混乱）和快速素数测试（可以是概率性的；它失败的情况不会影响算法的正确性，而且它们很少见，不会影响预期的 运行 时间）。

我不确定他是如何证明碰撞概率的正式界限的。我的大致思路基本上是，证明感兴趣的window中有足够多的素数，用中国剩余定理证明不可能一次碰撞太多的素数，得出碰撞概率受选择坏质数概率的限制，这个概率很低。但素数定理仅渐近成立，因此我们必须依靠计算机实验来了解机器字范围内素数的密度。不太好。