查看“︁费马素性检验”︁的源代码

{{noteTA|T=zh-cn:费马素性检验;zh-tw:費馬質數判定法;zh-hk:費馬質數判定法;|1=zh-cn:费马素性检验;zh-tw:費馬質數判定法;zh-hk:費馬質數判定法;|G1=Math}}
'''费马素性检验'''是一种[[質數判定法則]]，利用[[随机化算法]]判断一个数是[[合数]]还是''可能是''素数。

== 概念 ==
根据[[费马小定理]]：如果''p''是素数，<math>1 \le a \le p-1</math>，那么

:<math>a^{p-1} \equiv 1 \pmod{p}</math>。 

如果我们想知道''n''是否是素数，我们在中间选取''a''，看看上面等式是否成立。如果对于数值''a''等式不成立，那么''n''是合数。如果有很多的''a''能够使等式成立，那么我们可以说''n''可能是素数，或者[[伪素数]]。

在我们检验过程中，有可能我们选取的''a''都能让等式成立，然而n却是合数。这时等式

:<math>a^{n-1} \equiv 1 \pmod{n}</math>

被称为''Fermat liar''。如果我们选取满足下面等式的''a'' 

:<math>a^{n-1} \not\equiv 1 \pmod{n}</math>

那么''a''也就是对于''n''的合数判定的''Fermat witness''。

{|class="wikitable"
|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''是合数时輸出<u>合数</u>，否则輸出<u>可能是素数</u>：
:重复''k''次：
::在[2, ''n'' − 2]范围内随机选取''a''
::如果''a''<sup>''n'' − 1</sup> mod ''n'' ≠ 1那么返回<u>合数</u>
:返回<u>可能是素数</u>

若使用[[模指數運算]]的快速算法，这个算法的运行时间是O(''k''log<sup>2</sup>''n'' log log n) = Õ(''k'' log<sup>2</sup>''n'')，这里''k''是一个随机的''a''需要检验的次数，''n''是我们想要检验的数。

== 缺点 ==

众所周知，对于[[卡米歇爾數]]''n''，<u>全部</u>令gcd(''a'',''n'')=1的''a''都是費馬騙子數（Fermat liars）。尽管卡米歇爾數很是稀有，但是却足够令费马素性检验无法像如[[米勒-拉賓素性检验|米勒-拉賓]]和[[Solovay-Strassen primality test|Solovay-Strassen]]的[[素性检验]]般，成為被经常實際应用的素性检验。 

一般的，如果''n''不是卡米歇爾數，那么至少一半的

:<math>a\in(\mathbb{Z}/n\mathbb{Z})^*</math>

是費馬證人數（Fermat witnesses）。在这里，令''a''为費馬證人數、''a''<sub>1</sub>, ''a''<sub>2</sub>, ..., ''a''<sub>''s''</sub>为費馬騙子數。那么

:<math>(a\cdot a_i)^{n-1} \equiv a^{n-1}\cdot a_i^{n-1} \equiv a^{n-1} \not\equiv 1\pmod{n}</math>

所有的''a''×''a''<sub>i</sub> for ''i'' = 1, 2, ..., ''s''都是費馬證人數。

== 应用 ==

[[加密]]程序[[PGP]]在算法当中用到了这个素性检验方法。

== 参见 ==
* [[卢卡斯-莱默检验法]]
* [[埃拉托斯特尼筛法]]
* [[米勒-拉宾检验]]
* [[试除法]]
*[[孪生素数]]
*[[三胞胎素数]]
*[[四胞胎素数]]
*[[素数判定法则]]
*[[表兄弟素数]]
*[[六素数]]
*[[X²+1素数]]

== 参考 ==
* {{cite book |author={{tsl|en|Thomas H. Cormen||Thomas H. Cormen}}, {{tsl|en|Charles E. Leiserson||Charles E. Leiserson}}, [[罗纳德·李维斯特|Ronald L. Rivest]], {{tsl|en|Clifford Stein||Clifford Stein}} |title=[[算法导论|Introduction to Algorithms]] |edition=Second |publisher=MIT Press; McGraw-Hill |year=2001 |isbn=0-262-03293-7 |page=889–890 |chapter=Section 31.8: Primality testing}}
{{reflist}}

{{数论算法}}

[[Category:素性测试]]
[[Category:同余]]