费马素性检验

✍ dations ◷ 2025-07-11 17:04:55 #素性测试,同余

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

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

相关

  • 万维网万维网(英语:World Wide Web)亦作WWW、Web,是一个透过互联网访问的,由许多互相链接的超文本组成的系统。英国科学家蒂姆·伯纳斯-李于1989年发明了万维网。1990年他在瑞士CERN的
  • 面部神经麻痹贝尔氏麻痹症(Bell's palsy)是面部瘫痪之一种,由颅神经VII(面神经)的功能障碍引起,导致无力控制受影响一侧的面部肌肉。通常受影响一侧眼睛不能闭合。眼睛必须防止干燥,否则角膜可
  • 牛蒡牛蒡(学名:Arctium lappa;greater burdock;gobō (牛蒡/ゴボウ);edible burdock;lappa;beggar's buttons;thorny burr;happy major)是菊科牛蒡属的植物。本种又名东洋参、东洋牛鞭菜、
  • 北京物资学院北京物资学院(Beijing Wuzi University),简称 北物。学校位于中华人民共和国首都北京市通州区的财经类高等院校,隶属北京市教育委员会。学院以会计为特色,覆盖经济学、管理学等多
  • 中南暗沙中南暗沙因位于南中国海中沙群岛南部,故名。整个暗沙全部在海面以下,最浅处水深约272米。1983年公布名称为“中南暗沙”。
  • 莫妮卡·贝鲁奇莫妮卡·安娜·玛丽亚·贝鲁奇(意大利语:Monica Anna Maria Bellucci,1964年9月30日-),生于意大利温布利亚区卡斯泰洛城,意大利女演员与模特。莫妮卡·贝鲁奇出生于意大利翁布里亚
  • 娜斯娜斯(20世纪-),原名娜日斯(达斡尔语松树的意思)。专栏作家,自由撰稿人。她的文章主要关于对美国文化特别是纽约文化的观察,受其父母影响,对法国文化也有涉猎。主要表现为对电影电视的
  • 伍德莱克 (加利福尼亚州)伍德莱克(英文:Woodlake),是美国加利福尼亚州图莱里县下属的一座城市。建市于1941年9月23日,面积 大约为2.25平方英里 (5.8平方公里)。根据2010年美国人口普查,该市有人口7,279人
  • 台北101国际登高赛历年成绩列表台北101国际登高赛是自2005年起,每年在台北101举行的大楼登高比赛,除了各国好手争相较劲外,企业团体也借由这项比赛的参与,来凝聚团队向心力,而Paul Crake曾在2006年的新西兰自行
  • 神乐署坐标:39°52′44″N 116°24′20″E / 39.878827°N 116.405543°E / 39.878827; 116.405543神乐署位于北京天坛西门内稍南侧,坐西向东,是天坛五组大型建筑之一,是专司明清两代