卢卡斯-莱默检验法
卢卡斯-莱默检验法
数学中，卢卡斯-莱默检验法（）是检验梅森数的素性检验，是由爱德华·卢卡斯于1878年完善，德里克·亨利·莱默随后于1930年代将其改进。
因特网梅森素数大搜索用这个检验法找到了不少很大的素数，最近几个最大的素数就是这个项目发现的。由于梅森数比随机选择的整数更有可能是素数，因此他们认为这是一个极有用的方法。
方法.
卢卡斯－莱默检验法原理是这样：
令梅森数
"M""p" = 2"p"− 1作为检验对象（预设"p"是素数，否则"M""p"就是合数了）。
定义序列{"s""i" }：所有的"i" ≥ 0
.
.
这个序列的开始几项是4, 14, 194, 37634, ... （OEIS数列）
那么"M""p"是素数当且仅当
formula_1
否则, "M""p"是合数。
"s""p" − 2模"M""p"的余数叫做"p"的卢卡斯－莱默余数。
例子.
假设我们想验证M3 = 7是素数。我们从"s"=4开始，并更新3−2 = 1次，把所有的得数模7：
由于我们最终得到了一个能被7整除的"s"，因此M3是素数。
另一方面，M11 = 2047 = 23×89就不是素数。我们仍然从"s"=4开始，并更新11−2 = 9次，把所有的得数模2047：
由于"s"最终仍未能被2047整除，因此M11=2047不是素数。但是，我们从这个检验法仍然无法知道2047的因子，只知道它的卢卡斯-莱默余数1736。
正确性的证明.
我们注意到formula_2是一个具有闭式解的递推关系。定义formula_3及formula_4；我们可以用数学归纳法来验证对于所有"i"，都有formula_5：
formula_6。
formula_7
最后一个步骤可从formula_8推出。在两个部分中，我们都将用到这个结果。
充分性.
我们希望证明formula_9意味着formula_10是素数。我们叙述一个利用初等群论的证明，由J. W.布鲁斯给出。
假设formula_11。那么对于某个整数"k"，有formula_12，以及：
formula_13
现在假设"M""p"是合数，其非平凡素因子"q" > 2（所有梅森素数都是奇数）。定义含有"q"2个元素的集合formula_14，其中formula_15是模"q"的整数，是一个有限域。"X"中的乘法运算定义为：
formula_16.
由于"q" > 2，因此formula_17和formula_18位于X内。任何两个位于"X"内的数的乘积也一定位于"X"内，但它不是一个群，因为不是所有的元素"x"都有逆元素"y"，使得"xy" = 1。如果我们只考虑有逆元素的元素，我们便得到了一个群"X"*，它的大小最多为formula_19（因为0没有逆元素）。
现在，由于formula_20，且formula_21，我们有formula_22，根据方程(1)可得formula_23。两边平方，得formula_24，证明了formula_17是可逆的，其逆元素为formula_26，因此位于"X"*内，它的目能整除formula_27。实际上，这个阶必须等于formula_27，因为formula_29，因此这个阶不能整除formula_30。由于群元素的阶最多就是群的大小，我们便得出结论，formula_31。但由于"q"是formula_10的一个非平凡素因子，我们必须有formula_33，得出矛盾formula_34。因此formula_10是素数。
必要性.
我们假设formula_10是素数，欲推出formula_37。我们叙述一个Öystein J. R.
Ödseth的证明。首先，注意到3是模 "M""p"的二次非剩余，这是因为对于奇数"p" > 1，2 "p" − 1只取得值7 mod 12，因此从勒让德符号的性质可知formula_38是−1。根据欧拉准则，可得：
formula_39.
另一方面，2是模formula_10的二次剩余，这是因为formula_41，因此formula_42。根据欧拉准则，可得：
formula_43.
接着，定义formula_44，并像前面那样，定义"X"*为formula_45的乘法群。我们将用到以下的引理：
formula_46
（根据费马小定理），以及
formula_47
对于所有整数"a"（费马小定理）。
那么，在群"X"*中，我们有：
formula_48
简单计算可知 formula_49。我们可以用这个结果来计算群"X"*中的formula_50：
formula_51
其中我们用到了以下的事实：
formula_52。
由于formula_53，我们还需要做的就是把方程的两边乘以formula_54，并利用formula_55：
formula_56
由于"s""p"−2是整数，且在"X"*内是零，因此它也是零mod "M""p"。
本站由爱斯园团队开发维护，感谢那些提出宝贵意见和打赏的网友，没有你们的支持，网站不可能发展到今天，
继往开来，善终如始，我们将继续砥砺前行。
Copyright ©2014 iissy.com, All Rights Reserved.