费马素性检验

✍ dations ◷ 2025-07-19 06:45:32 #素性测试,同余

费马素性检验是一种素数判定法则,利用随机化算法判断一个数是合数还是素数。

根据费马小定理:如果是素数, 1 a p 1 {\displaystyle 1\leq a\leq p-1} 是否是素数,我们在中间选取,看看上面等式是否成立。如果对于数值等式不成立,那么是合数。如果有很多的能够使等式成立,那么我们可以说可能是素数,或者伪素数。

在我们检验过程中,有可能我们选取的都能让等式成立,然而n却是合数。这时等式

被称为。如果我们选取满足下面等式的

那么也就是对于的合数判定的。

整个算法可以写成是下面两大部:

若使用模指数运算的快速算法,这个算法的运行时间是O(×log3),这里是一个随机的需要检验的次数,是我们想要检验的数。

众所周知,对于卡米歇尔数,全部令gcd(,)=1的都是费马骗子数(Fermat liars)。尽管卡米歇尔数很是稀有,但是却足够令费马素性检验无法像如米勒-拉宾和Solovay-Strassen的素性检验般,成为被经常实际应用的素性检验。

一般的,如果不是卡米歇尔数,那么至少一半的

是费马证人数(Fermat witnesses)。在这里,令为费马证人数、1, 2, ..., 为费马骗子数。那么

所有的×i for = 1, 2, ..., 都是费马证人数。

加密程序PGP在算法当中用到了这个素性检验方法。

相关

  • 哈雷迪哈雷迪犹太教(希伯来语:.mw-parser-output .script-hebrew,.mw-parser-output .script-Hebr{font-size:1.15em;font-family:"Ezra SIL","Ezra SIL SR","Keter Aram Tsova","Ta
  • 细胞生物细胞(英语:Cell)旧称䏭,是生物体结构和功能的基本单位。它是除了病毒之外所有具有完整生命力的生物的最小单位,也经常被称为生命的积木(病毒仅由DNA/RNA组成,并由蛋白质和脂肪包裹
  • 纳瓦拉国王纳瓦拉君主是指历来纳瓦拉王国的王位继承人。特奥巴尔多一世是桑乔七世的外甥、桑乔六世的外孙。在这段时期,纳瓦拉王位由法国国王兼领,直至查理四世无男性子嗣。胡安娜二世和
  • 瑜伽论龙树、圣天、无著、世亲、陈那、法称、释迦光、功德光 【其他】─《入中论》《释量论》《俱舍论》《现观庄严论》《戒律本论》【其他】─ 《《瑜伽师地论》(梵语:Yogācāra
  • 主动搜寻地外文明计划搜寻外星高智生命活动 (Active Search for Extra-Terrestrial Intelligence),是尝试寄发讯息给有智慧的外星人的活动,现行的搜寻外星高智生命讯息通常都是无线电的形式,不过实
  • 曼谷王朝泰国中部:泰国北部:泰国南部:扎克里王朝(泰语:ราชวงศ์จักรี,皇家转写:Ratchawong Chakkri,泰语发音:),也译作却克里王朝、查克里王朝,又称曼谷王朝,是从1782年起延续至今的泰
  • 美国螯虾克氏原螯虾(学名:Procambarus clarkii),原产于美国东南部,又名美国螯虾、路易斯安那州螯虾,中华人民共和国称小龙虾,属蝲蛄科,在中国北方某些地区被直接称为“蝲蛄”,是最具食用价值
  • 2018年夏季青年奥林匹克运动会举重比赛2018年夏季青年奥林匹克运动会举重比赛于2018年10月7日至13日在布宜诺斯艾利斯岩石体育中心公园举行。所有参加该届夏季青年奥运会举重比赛的运动员皆须于2001年1月1日至200
  • 中国散裂中子源中国散裂中子源(英语:China Spallation Neutron Source,缩写CSNS)是在中国广东省东莞市大朗镇建设、由中国科学院高能物理研究所运营的一个基于粒子加速器的中子源,也是中国南方
  • 四顶点定理四顶点定理是微分几何关于平面曲线的整体性质的定理。这定理指出,一条简单闭曲线的曲率函数,如果不是常值,便有至少四个局部极值。更确切地说,这函数有至少两个局部极大值和两个