卢卡斯-莱默检验法

✍ dations ◷ 2025-04-03 10:32:11 #素性测试

数学中,卢卡斯-莱默检验法(英语: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 

相关

  • 恶魔蠕虫恶魔蠕虫(学名:Halicephalobus mephisto)也称魔鬼蠕虫、魔鬼线虫,是2011年在南非一座金矿中发现的一种新线虫,生活在地面以下1.3公里深的极端环境中,身长约0.5毫米。
  • 教研人员教师(英语:Teachers,中文口语也常称作“老师”,旧称“先生”),又称作教育工作者、教员,是大众对教育从业者的称呼,是培养社会所需人才的专业。于教育机构;因应社会需要,亦有家庭教师的
  • 单胺类神经递质单胺神经递质(英语:monoamine neurotransmitter)是含有芳乙胺结构的神经递质和神经调质,所有单胺类都是从芳香族氨基酸(苯丙氨酸、酪氨酸、色氨酸)和甲状腺激素衍生而来,经芳香族L-
  • 佛祖佛祖可以指:
  • 花蝇科花蝇科(学名:Anthomyiidae)是双翅目短角亚目(德语:Fliegen)的成员,是家蝇总科(英语:Muscoidea)之下的一个庞大而且高度多样性的科级分类单元。在全世界范围内,已知这一群体中约有1200种
  • 古叙利亚叙利亚是世界最古老文明发源地之一。7世纪以前,叙利亚是基督教的发祥地和传播中心;伊斯兰教在中东地区的扩张,7世纪到16世纪初叶一直是伊斯兰教传播中心之一;由于土耳其和十字军
  • 黄颡鱼黄颡鱼(学名:)又称 疯鲿,是鲶形目鲿科一种常见的底栖性淡水鱼,主要分布于中国长江水系和珠江水系。在长江上游川渝、贵州俗名 黄辣丁,下游江苏、上海和浙江一带俗称 䱀䲉鱼(吴语音:a
  • 井卷久一井卷久一((日文)いまき ひさかず,1942年12月5日-)曾任日本马自达汽车公司的第13任社长,亦曾获得2006年RJC年度风云人物奖,最大的嗜好是摄影。由于美国福特汽车曾是该公司最大的股东,
  • 俱姓俱姓(汉语拼音:jū),一个中国姓氏,人数较少。俱姓,为中国东晋末十六国时期后秦俱罗氏所改。寻访稀罕姓系列报道(八十七):俱(jū)家5兄妹 外号都叫“俱乐部”(图)连接内资源是旁人半开玩笑
  • 纪君祥纪君祥(?年-?年),元代戏曲作家,大都人。一作纪天祥,生卒年不详。著有杂剧6种,现仅存1种:《赵氏孤儿冤报冤》,一作《赵氏孤儿大报仇》,简称《赵氏孤儿》。另《陈文图悟道松阴梦》1剧,仅存