卢卡斯-莱默检验法

数学中，卢卡斯-莱默检验法（英语：Lucas–Lehmer primality test）是检验梅森数的素性检验，是由爱德华·卢卡斯于1878年完善，德里克·亨利·莱默随后于1930年代将其改进。

因特网梅森素数大搜索用这个检验法找到了不少很大的素数，最近几个最大的素数就是这个项目发现的。由于梅森数比随机选择的整数更有可能是素数，因此他们认为这是一个极有用的方法。

卢卡斯－莱默检验法原理是这样：
令梅森数 = 2− 1作为检验对象（预设是素数，否则就是合数了）。

定义序列{ }：所有的 ≥ 0

这个序列的开始几项是4, 14, 194, 37634, ... （OEIS中的数列A003010）

那么是素数当且仅当

否则, 是合数。
_{− 2}模的余数叫做的卢卡斯－莱默余数。

假设我们想验证M₃ = 7是素数。我们从=4开始，并更新3−2 = 1次，把所有的得数模7：

由于我们最终得到了一个能被7整除的，因此M₃是素数。

另一方面，M₁₁ = 2047 = 23×89就不是素数。我们仍然从=4开始，并更新11−2 = 9次，把所有的得数模2047：

由于最终仍未能被2047整除，因此M₁₁=2047不是素数。但是，我们从这个检验法仍然无法知道2047的因子，只知道它的卢卡斯-莱默余数1736。

我们注意到${\displaystyle ⟨<!--\; ⟨\; -->s_i⟩<!--\; ⟩\; -->}$，都有${\displaystyle s_i={\mathrm{\omega <!--\; \omega \; -->}}^{2^i}+{\stackrel{¯<!--\; ¯\; -->}{\mathrm{\omega <!--\; \omega \; -->}}}^{2^i}}$，有${\displaystyle {\mathrm{\omega <!--\; \omega \; -->}}^{2^{p-<!--\; -\; -->2}}+{\stackrel{¯<!--\; ¯\; -->}{\mathrm{\omega <!--\; \omega \; -->}}}^{2^{p-<!--\; -\; -->2}}=k{M}_p}$是合数，其非平凡素因子 > 2（所有梅森素数都是奇数）。定义含有2个元素的集合${\displaystyle X=\{a+b\sqrt{3}|a,b\in <!--\; \in \; -->{\mathbb{Z}}_q\}}$的整数，是一个有限域。中的乘法运算定义为：

由于 > 2，因此${\displaystyle \mathrm{\omega <!--\; \omega \; -->}}$内的数的乘积也一定位于内，但它不是一个群，因为不是所有的元素都有逆元素，使得 = 1。如果我们只考虑有逆元素的元素，我们便得到了一个群*，它的大小最多为${\displaystyle q^2-<!--\; -\; -->1}$*内，它的目能整除${\displaystyle 2^p}$是${\displaystyle M_p}$的二次非剩余，这是因为对于奇数 > 1，2  − 1只取得值7 mod 12，因此从勒让德符号的性质可知${\displaystyle (3|M_p)}$*为${\displaystyle \{a+b\sqrt{3}|a,b\in <!--\; \in \; -->{\mathbb{Z}}_{M_p}\}}$（费马小定理）。

那么，在群*中，我们有：

简单计算可知 ${\displaystyle \mathrm{\omega <!--\; \omega \; -->}=(6+\mathrm{\sigma <!--\; \sigma \; -->}{)}^2/24}$*中的${\displaystyle {\mathrm{\omega <!--\; \omega \; -->}}^{(M_p+1)/2}}$₋₂是整数，且在*内是零，因此它也是零mod 。