费马素性检验

✍ dations ◷ 2025-10-23 01:35:13 #素性测试,同余

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

根据费马小定理:如果是素数, 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在算法当中用到了这个素性检验方法。

相关

  • 核技术核子技术是关于原子核的核反应技术,其中比较重要和已经投入实用的有核动力、核医学和核武器。核技术的应用十分广泛,也应用于烟雾探测器(英语:Smoke detector),到瞄准具。1896年,亨
  • 海军军官学校中华民国海军军官学校(R.O.C. Naval Academy),简称海军官校,是一所专门培育中华民国海军军官的军校,位于中华民国高雄市左营区海军左营基地,以“培育第一等人才,建设第一等海军”为
  • 个人个人(意大利语、西班牙语: Persona,英语、德语: Person,来自拉丁语: Persōna)是单独的人类个体的简称,相对应的是由多数人类个体组成的人民。亦是具有某种能力或属性的存在,如理
  • 温哥华岛温哥华岛(英语:Vancouver Island:法语:Île de Vancouver)位于加拿大不列颠哥伦比亚的西南隅。该岛长460公里(285英里),宽50-80公里(30-50英里),面积达31,285平方公里(12,221平方英里),是
  • 比尔赌场比尔赌场(Bill's Gamblin' Hall and Saloon)是位于美国内华达州拉斯维加斯赌城大道上的一间赌场酒店,由哈拉斯娱乐所持有及营运。酒店建于1979年,只有196间客房,是拉斯维加斯大道
  • 超临界水反应堆超临界水反应堆(英语:Supercritical water reactor,缩写:SCWR)是一种第四代反应堆设计,使用超临界水作为工作流体。超临界水反应堆也是一种轻水反应堆(LWR),但是工作流体运作于较高的
  • 莉姆·阿布达拉赞莉姆·阿布达拉赞(Reem Abdalazem,1992年11月25日-)是一名埃及花样游泳运动员。她代表埃及参加奥林匹克运动会和世界游泳锦标赛。
  • 浅川智惠子浅川智惠子(日语:浅川智恵子,1958年-)是一位日本盲人计算机科学家,主要研究无障碍环境。她在IBM研究院东京研究实验室无障碍研究中心担任高级研究员,获评“IBM杰出工程师”。她开发
  • 班布尔善班布尔善(1617年-1669年),也有译为“巴穆布尔善”,满洲爱新觉罗氏,为人足智多谋。清太祖努尔哈赤第六子悫厚辅国公塔拜第四子。崇德四年(1639年),袭三等奉国将军。顺治元年(1644年),以功
  • 李彬 (明将领)李彬(1361年-1422年),字质文,谥刚毅,河南江北等处行中书省安丰路濠州定远县(今安徽省定远县)人,明朝军事将领,丰城侯。李彬父亲李信早年跟随朱元璋起兵,累功至济川卫指挥佥事。李彬后继