Rabin-Miller 强伪素数检验

一种素性检验，它提供了一种有效的概率算法，用于确定给定数字是否为素数。它基于强伪素数的性质。

该算法的步骤如下。给定一个奇数整数 ，令 ，其中 为奇数。然后选择一个随机整数 ，其中 。如果 或对于某个 ，，则 通过测试。一个素数将对所有 通过测试。

该测试非常快速，并且需要不超过 次乘法运算（模 ），其中 lg 是以 2 为底的对数。不幸的是，一个通过测试的数字不一定是素数。Monier (1980) 和 Rabin (1980) 已经证明，对于最多 1/4 的可能基数 ，合数会通过测试。如果对一个合数执行 次独立的测试，那么它通过每次测试的概率为 或更小。

然而，如果预先知道通过特定测试集的最小合数，那么该测试集就构成了对所有较小数的素性证明。使用前 个素数进行多次 Rabin-Miller 测试时，通过测试的最小奇数序列（对于 , 2, ...）由 2047, 1373653, 25326001, 3215031751, 2152302898747, 3474749660383, 341550071728321, 341550071728321, ... 给出 (OEIS A014233; Jaeschke 1993)。因此，使用前 7 个素数（使用 8 个素数没有改进）的多次 Rabin 测试对于高达 的每个数字都是有效的。

Wolfram 语言在基数 2 和 3 中结合 Lucas 伪素数测试实现了多次 Rabin-Miller 测试，作为函数使用的素性检验PrimeQ[n]。截至 1997 年，已知此过程仅对所有 是正确的，但没有已知的反例，如果存在任何反例，预计它们出现的概率极小（即，远小于计算机执行测试时发生硬件错误的概率）。