费马素性检验

✍ dations ◷ 2025-10-19 20:34:53 #素性测试,同余

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

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

相关

  • 模式识别受体模式识别受体为免疫系统细胞表达的,与病原微生物或细胞应激相关的蛋白。可以被模式识别受体识别的微生物特定分子为病原相关分子模式。包括细菌的碳水化合物(如脂多糖和甘露
  • 的里雅斯特省的里雅斯特省(Provincia di Trieste)是意大利弗留利-威尼斯朱利亚的一个省。面积212平方公里,2004年人口240,000人。首府的里雅斯特。下分6市镇。
  • 萨顿萨顿可以指:
  • 单型属单型(英语:Monotypic)在生物分类学上,是指一个分类群中只含有唯一的一个类型。而植物分类学及动物分类学之间,对“单型”的用法又不甚相同:
  • 通商口岸商埠,又称“通商口岸”,是一个国家向外开放的特定通商地区。近代历史中曾存在于中国、日本、朝鲜等国家。商埠最早存在于实行锁国政策的国家。在中国,自明朝和清朝两度宣布海禁
  • 高氙酸钠高氙酸钠(Na4XeO6)是高氙酸的钠盐。白色粉末,有八水、六水、二水、半水和无水等形式。无水高氙酸钠可由半水物在>100°C下烘干而得到。它在200-360°C时才分解。干燥后的高氙酸
  • 㭴田Reo樫田レオ(日语:かしだ レオ )是日本的自由游戏剧本作家。岐阜县出身,生日是3月5日。主要在Key的作品中担当辅助的剧本作家。在2005年11月25日Key发售的智代After ~It's a Wonder
  • 牛莉牛莉(1972年5月1日-),中华人民共和国女演员,出生于河北省石家庄的一个运动员世家。1986年取得全国第一届女子花样游泳团体冠军,1990年取得中国人民解放军全军女子射击冠军,因此在体
  • 宇宙泛星系偏振背景成像宇宙泛星系偏振背景成像(英文:Background Imaging of Cosmic Extragalactic Polarization,缩写:BICEP)是一系列宇宙微波背景实验,专注于测量宇宙微波背景辐射的偏振,特别是B模偏振
  • 张玑张玑(1422年-?),字宗璿,山东济南府齐东县人,民籍,明朝政治人物。进士出身。山东乡试第十五名。景泰二年(1451年),参加辛未科会试,得贡士第九十九名。殿试登进士第二甲第五十五名。曾祖父