Thomas H. Cormen(英语:Thomas H. Cormen), Charles E. Leiserson(英语:Charles E. Leiserson), Ronald L. Rivest, Clifford Stein(英语:Clifford Stein). Section 31.8: Primality testing. Introduction to Algorithms Second. MIT Press; McGraw-Hill. 2001: 889–890. ISBN 0-262-03293-7.
十月 25, 2023
费马素性检验, 是一种質數判定法則, 利用随机化算法判断一个数是合数还是可能是素数, 目录, 概念, 算法以及运行时间, 缺点, 应用, 参见, 参考概念, 编辑根据费马小定理, 如果p是素数, displaystyle, nbsp, 那么, displaystyle, equiv, pmod, nbsp, 如果我们想知道n是否是素数, 我们在中间选取a, 看看上面等式是否成立, 如果对于数值a等式不成立, 那么n是合数, 如果有很多的a能够使等式成立, 那么我们可以说n可能是素数, 或者伪素数, 在我们检验过程中. 费马素性检验是一种質數判定法則 利用随机化算法判断一个数是合数还是可能是素数 目录 1 概念 2 算法以及运行时间 3 缺点 4 应用 5 参见 6 参考概念 编辑根据费马小定理 如果p是素数 1 a p 1 displaystyle 1 leq a leq p 1 nbsp 那么 a p 1 1 mod p displaystyle a p 1 equiv 1 pmod p nbsp 如果我们想知道n是否是素数 我们在中间选取a 看看上面等式是否成立 如果对于数值a等式不成立 那么n是合数 如果有很多的a能够使等式成立 那么我们可以说n可能是素数 或者伪素数 在我们检验过程中 有可能我们选取的a都能让等式成立 然而n却是合数 这时等式 a n 1 1 mod n displaystyle a n 1 equiv 1 pmod n nbsp 被称为Fermat liar 如果我们选取满足下面等式的a a n 1 1 mod n displaystyle a n 1 not equiv 1 pmod n nbsp 那么a也就是对于n的合数判定的Fermat witness a 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30最小的n值 4 341 91 15 4 35 6 9 4 9 10 65 4 15 14 15 4 25 6 21 4 21 22 25 4 9 26 9 4 49算法以及运行时间 编辑整个算法可以写成是下面两大部 输入 n需要检验的数 k 参数之一来决定检验需要进行的次数 输出 当n是合数时輸出合数 否则輸出可能是素数 重复k次 在 2 n 2 范围内随机选取a 如果an 1 mod n 1那么返回合数 dd 返回可能是素数若使用模指數運算的快速算法 这个算法的运行时间是O klog2n log log n O k log2n 这里k是一个随机的a需要检验的次数 n是我们想要检验的数 缺点 编辑众所周知 对于卡米歇爾數n 全部令gcd a n 1的a都是費馬騙子數 Fermat liars 尽管卡米歇爾數很是稀有 但是却足够令费马素性检验无法像如米勒 拉賓和Solovay Strassen的素性检验般 成為被经常實際应用的素性检验 一般的 如果n不是卡米歇爾數 那么至少一半的 a Z n Z displaystyle a in mathbb Z n mathbb Z nbsp 是費馬證人數 Fermat witnesses 在这里 令a为費馬證人數 a1 a2 as为費馬騙子數 那么 a a i n 1 a n 1 a i n 1 a n 1 1 mod n displaystyle a cdot a i n 1 equiv a n 1 cdot a i n 1 equiv a n 1 not equiv 1 pmod n nbsp 所有的a ai for i 1 2 s都是費馬證人數 应用 编辑加密程序PGP在算法当中用到了这个素性检验方法 参见 编辑卢卡斯 莱默检验法 埃拉托斯特尼筛法 米勒 拉宾检验 试除法 孪生素数 三胞胎素数 四胞胎素数 素数判定法则 表兄弟素数 六素数 X 1素数参考 编辑Thomas H Cormen 英语 Thomas H Cormen Charles E Leiserson 英语 Charles E Leiserson Ronald L Rivest Clifford Stein 英语 Clifford Stein Section 31 8 Primality testing Introduction to Algorithms Second MIT Press McGraw Hill 2001 889 890 ISBN 0 262 03293 7 取自 https zh wikipedia org w index php title 费马素性检验 amp oldid 71553507, 维基百科,wiki,书籍,书籍,图书馆,