卢卡斯-莱默检验法

✍ dations ◷ 2025-07-19 07:18:17 #素性测试

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

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

卢卡斯-莱默检验法原理是这样:
令梅森数 = 2− 1作为检验对象(预设是素数,否则就是合数了)。

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

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

那么是素数当且仅当

否则, 是合数。
− 2的余数叫做的卢卡斯-莱默余数。

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

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

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

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

我们注意到 s i {\displaystyle {\langle }s_{i}{\rangle }} ,都有 s i = ω 2 i + ω ¯ 2 i {\displaystyle s_{i}=\omega ^{2^{i}}+{\bar {\omega }}^{2^{i}}} ,有 ω 2 p 2 + ω ¯ 2 p 2 = k M p {\displaystyle \omega ^{2^{p-2}}+{\bar {\omega }}^{2^{p-2}}=kM_{p}} 是合数,其非平凡素因子 > 2(所有梅森素数都是奇数)。定义含有2个元素的集合 X = { a + b 3 | a , b Z q } {\displaystyle X=\{a+b{\sqrt {3}}|a,b\in \mathbb {Z} _{q}\}} 的整数,是一个有限域。中的乘法运算定义为:

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

那么,在群*中,我们有:

简单计算可知 ω = ( 6 + σ ) 2 / 24 {\displaystyle \omega =(6+\sigma )^{2}/24} *中的 ω ( M p + 1 ) / 2 {\displaystyle \omega ^{(M_{p}+1)/2}} −2是整数,且在*内是零,因此它也是零mod 

相关

  • 运动防护员运动防护员(英语:Athletic Trainer,简称AT),又称运动训练员,是一种需考取专业证照之运动医学专业人员,专门从事运动防护以及运动训练等等工作。其中,运动防护是指各种体育运动之预防
  • 奥格列汀奥格列汀,即Omarigliptin (MK-3102) ,是一种强效且长效的口服用抗糖尿病药,是一类DPP-4抑制剂。该药物致力于使得2型糖尿病患者能够将用药频率降低到一周一次。该药物由默克药
  • 集成电路集成电路(英语:integrated circuit,缩写作 IC;德语:integrierter Schaltkreis),或称微电路(microcircuit)、微芯片(microchip)、芯片(chip)在电子学中是一种将电路(主要包括半导体设备,也包
  • 德国之翼航空9525号班机空难德国之翼航空9525号航班(德语:Germanwings-Flug 9525,航班编号:4U9525),2015年3月24日由西班牙巴塞罗那飞往德国杜塞尔多夫,途经法国南部上普罗旺斯阿尔卑斯省上空时失事,于法国境内
  • 即期券即期券是美国纸币的一种,发行于1861年8月至1862年4月美国南北战争期间,面额有5美元、10美元、20美元。即期券是美国发行的第一种纸币,在某种意义上,广泛流传到今天的一系列的货
  • 卡美哈梅哈四世卡美哈梅哈四世(Kamehameha IV,1834年-1863年)原名亚历山大·伊奥拉尼·利霍利霍·柯阿威努伊(Alexander ʻIolani Liholiho Keawenui),是夏威夷王国第四代国王,1855年1月11日至1863
  • 老艾伯特·戈尔老艾伯特·阿诺德·“阿尔”·戈尔(Albert Arnold "Al" Gore, Sr.,1907年12月26日-1998年12月5日),美国政治家,美国民主党成员,曾任美国参议院议员(1953年-1971年)。老艾伯特是美国前
  • 常遇春常遇春像,取自清代上官周《晚笑堂画传》常遇春(1330年-1369年8月9日),字伯仁,号燕衡。祖籍南直隶怀远(今属安徽),和阳(和州,今安徽和县)人,明朝开国军事大将。本封鄂国公,追封开平王,谥忠武
  • 陈爱美陈爱美(1953年-)。现任陕西电视台播音指导、节目主持人,陕西省第九届政协委员,中国电视艺术家协会主持人委员会副会长等职。祖籍山东,出生在陕西阎良;北京广播学院新闻编采专业毕业
  • 埃列娜公主 (罗马尼亚)埃列娜(Elena,1950年11月5日-),出生于瑞士洛桑。罗马尼亚公主,前霍亨索伦公主。是罗马尼亚末代国王米哈伊一世与王后波旁-帕尔马的安妮公主的次女。埃列娜公主是罗马尼亚王位第2顺