费马素性检验
(重定向自費馬質數判定法)
概念编辑
根据费马小定理:如果p是素数, ,那么
- 。
如果我们想知道n是否是素数,我们在中间选取a,看看上面等式是否成立。如果对于数值a等式不成立,那么n是合数。如果有很多的a能够使等式成立,那么我们可以说n可能是素数,或者伪素数。
在我们检验过程中,有可能我们选取的a都能让等式成立,然而n却是合数。这时等式
被称为Fermat liar。如果我们选取满足下面等式的a
那么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那么返回合数
- 返回可能是素数
若使用模指數運算的快速算法,这个算法的运行时间是O(klog2n log log n) = Õ(k log2n),这里k是一个随机的a需要检验的次数,n是我们想要检验的数。
缺点编辑
众所周知,对于卡米歇爾數n,全部令gcd(a,n)=1的a都是費馬騙子數(Fermat liars)。尽管卡米歇爾數很是稀有,但是却足够令费马素性检验无法像如米勒-拉賓和Solovay-Strassen的素性检验般,成為被经常實際应用的素性检验。
一般的,如果n不是卡米歇爾數,那么至少一半的
是費馬證人數(Fermat witnesses)。在这里,令a为費馬證人數、a1, a2, ..., as为費馬騙子數。那么
所有的a×ai for i = 1, 2, ..., s都是費馬證人數。
应用编辑
参见编辑
参考编辑
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Section 31.8: Primality testing. Introduction to Algorithms Second. MIT Press; McGraw-Hill. 2001: 889–890. ISBN 0-262-03293-7.
🔥 Top keywords: Baike: 首页Special:搜索胖猫跳江事件背着善宰跑九龍城寨之圍城逆天奇案2璩静淚之女王歌手2024Energy (組合)新生 (网络剧)习近平匈牙利邊佑錫劉俊謙 (香港)金智媛神耆小子塞尔维亚金秀賢 (男演員)母亲节猩球崛起:王國誕生九龍寨城馴鹿寶貝家族榮耀之繼承者Seventeen (組合)六四事件不夠善良的我們张维为楊佩潔TripleS支配物种庆余年郭葦昀洪若潭命案金惠奫2024年英雄联盟季中邀请赛春色寄情人BABYMONSTER笑看風雲乘風2024排球少年!!角色列表破墓徐巧芯中华人民共和国中華民國打天下2WIND BREAKER—防風少年—习明泽排球少年!!彭丽媛磁暴ILLIT贾斯汀·比伯逆天奇案BOYNEXTDOOR猿人爭霸戰:猩凶革命張書偉我的婆婆怎麼那麼可愛我獨自升級怪獸8號謝坤達IVE (組合)與鳳行關於我轉生變成史萊姆這檔事角色列表黃道十二宮福建號航空母艦虽然不是英雄葉乃文五月天張員瑛草榴社区張文傑2024年花蓮地震极光香緹·摩爾迷宮飯呂家愷搜查班長1958日本劉德華海莉·鮑德溫蕭景鴻越位 (足球)葬送的芙莉蓮周處除三害 (電影)毛泽东願榮光歸香港林峯周雨彤伍允龍羅毓儀香港Baike: 分類索引沒有秘密猩球崛起:終極決戰角質層唐振剛柯佳嬿文化大革命