我正在阅读 Sedgewick 的 Rabin-Karb 算法。书上说：
我们使用随机素数 Q 取尽可能大的值，同时避免溢出
在第一次阅读时，我没有注意到随机的重要性，当我看到代码long中使用了 a 时，我的第一个想法是：
a）使用 Eratosthene 的筛子找到适合 along
或
b）从列表中查找质数任何足够大且大于的质数int并将其用作常数。
但是其余的解释说：
我们将使用一个
long大于10^20使发生碰撞的概率小于的值10^-20
这部分让我感到困惑，因为 along不适合10^20更不用说大于那个值了。然后，当我检查素数的计算时，这本书遵循了一个只有以下提示的练习：
一个随机的 n 位数是质数，概率与 1/n 成正比
这意味着什么？
所以基本上我没有得到的是：
a）使用随机素数是什么意思？为什么我们不能预先计算它并将其用作常数？
b）为什么10^20提到它，因为它超出了范围long？
c) 这个提示有什么帮助？究竟是什么意思？
再一次，Sedgewick 试图简化算法，但在细节上略有错误。首先，正如您所观察到的，10 20不能用 64 位表示。然而，即使取一个接近 2 63 − 1 的素数，您可能还需要一点空间以正常方式相乘而不会溢出，以便随后的模数是正确的。答案使用 31 位素数，这使得这很容易，但仅提供 10 -9范围内的碰撞概率。
原始版本使用Rabin 指纹和2 [x]上的随机不可约多项式，从代数数论的角度来看，它的行为很像整数上的随机素数。如果我们选择多项式为 32 或 64 次，那么指纹完全适合适当长度的计算机字，并且多项式加法和减法都可以按位异或，因此不会溢出。
现在，Sedgewick 大概不想解释多项式环是如何工作的。美好的。如果我必须在实践中实施这种方法，我会选择一个接近最大值的素数 p ，它很容易用廉价的指令进行修改（我偏爱2 31 - 2 27 + 1；实际上编辑 2 31 - 1效果更好，因为我们在这里不需要平滑素数），然后在 [1, p−1] 中选择一个随机数来评估多项式（这是维基百科的解释）。我们需要一些随机性的原因是，否则不经意的对手可能会选择一个保证有很多哈希冲突的输入，这会严重降低运行时间。
然而，Sedgewick 想要更接近原始版本，但它本质上是在 x 的固定值处评估多项式（在使用多项式环的原始版本中字面意思是 x）。他需要一个随机素数，这样不经意间的对手就无法设计碰撞。筛选足够大的数字是非常低效的，所以他求助于素数定理（这是他暗示背后的数学，但它只是渐近地成立，这在理论上会造成很大的混乱）和快速素数测试（可能是概率的；失败的情况不会影响算法的正确性，而且它们非常罕见，不会影响预期的运行时间）。
我不确定他如何证明碰撞概率的正式界限。我的粗略想法基本上是，证明感兴趣的窗口中有足够的素数，使用中国剩余定理证明一次不可能有太多素数发生碰撞，得出碰撞概率由选择坏素数的概率很低。但是素数定理只是渐近地成立，所以我们必须依靠计算机实验来确定机器字范围内素数的密度。不是很好。