卢卡斯-莱默检验法

✍ dations ◷ 2025-07-08 15:27:37 #素性测试

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

相关

  • 恒温动物恒温动物(Homeotherms),俗称温体动物,与内温动物(Endotherms)不 同。在动物学指的是那些能够调节自身体温的动物,其活动性并不像变温动物那样依赖外界温度。在鸟和哺乳动物会通过新
  • 阿尔弗雷德·诺贝尔阿尔弗雷德·伯恩哈德·诺贝尔(瑞典语:Alfred Bernhard Nobel,/noʊˈbɛl/;瑞典语:.mw-parser-output .IPA{font-family:"Charis SIL","Doulos SIL","Linux Libertine","Segoe U
  • 竞技运动场馆竞技场(拉丁语:arena),建筑学指场地四周被倾斜的阶梯式看台(英语:Seating assignment)环绕的设施,例如罗马斗兽场、体育场、剧场。竞技场在竞技比赛等场合可指中心的场地,也可指包括
  • 合众社合众国际社(英文:United Press International,缩写:UPI),美国著名通讯社之一,总部位于美国华盛顿特区,使用英文、西班牙文和阿拉伯文向世界各地发布新闻和评论。其前身为1907年成立
  • 存在锁链存在锁链(英语:Chain of being),18世纪欧洲神学的概念,是自上而下万物的分级。在“存在锁链”中,上帝居首,其下有九个等级的天使,天使之下是人类,其下为动物、植物、矿物。锁链中任何
  • 癸烷正癸烷是化学式为CH3(CH2)8CH3的烷烃,总共有136种异构体,若不计立体异构则为75个,全都是可燃液体。癸烷是汽油的组分之一。与其他烷烃类似,癸烷是非极性分子,不易溶于水之类的极
  • 量日仪太阳仪(英语:Heliometer,来自希腊文“太阳”和“量测”)是一个原始设计作为量测不同季节时太阳直径差异的仪器。太阳仪的基本概念就是置入一个分割成两半的元件在望远镜光路上以
  • 利翁·福伊希特万格利翁·福伊希特万格(Lion Feuchtwanger,笔名:J.L. Wetcheek,1884年7月7日出生于德国慕尼黑,1958年12月21日逝世于美国洛杉矶)是一位德国犹太小说作家。福伊希特万格出生于一个犹太
  • 蔡肇祺蔡肇祺(1933年2月14日-2018年9月11日),曾号燕青,生于台湾台南,祖籍福建漳州,药师、诗人、词曲作家与武术家。毕生诗词创作甚丰,并为两千余首诗词谱曲。为太极拳宗师郑曼青先生入室弟
  • 盖士利盖士利(1858年3月11日-1925年11月7日),原名威廉·沃特·卡塞尔斯(William Wharton Cassels),是一位英国圣公会传教士,圣公会华西教区首任主教。盖士利出生于葡萄牙波尔图,就读于英国