卢卡斯-莱默检验

卢卡斯-莱默检验是一种高效的确定性 素性检验，用于确定 梅森数 是否为素数。由于已知梅森数只有在素数下标时才可能是素数，因此可以将注意力限制为形如 的梅森数，其中 是一个 奇素数。

考虑以下递推方程

(1)

其中 。例如，忽略同余，此迭代的前几个项为 4, 14, 194, 37634, 1416317954, ... (OEIS A003010)。

结果表明， 是素数 当且仅当 ，且值 称为 的卢卡斯-莱默剩余。

例如，对于 获得的序列为 4, 14, 67, 42, 111, 0，因此 是素数。

对于素数 ，前几个卢卡斯-莱默剩余为 1, 0, 0, 0, 1736, 0, 0, 0, 6107895, 458738443, 0, 117093979072, ... (OEIS A095847)。

此检验也可以扩展到任意 整数。在普拉特 (1975) 的工作之前，卢卡斯-莱默检验一直被纯粹视为一种启发式方法，在很多时候都有效 (Knuth 1969)。普拉特 (1975) 表明，通过将莱默的素性启发式方法递归地应用于 的因子，可以使之成为一种非确定性程序，从而产生一种素性证明，即后来的 普拉特证书。

卢卡斯-莱默检验的广义版本允许

(2)

其中 是不同的 素因子， 是它们各自的 幂。如果存在一个 卢卡斯序列 使得

(3)

对于 , ..., 并且

(4)

那么 是一个 素数。这简化为 梅森数 的传统卢卡斯-莱默检验。