费马素性检验
![本页使用了标题或全文手工转换](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
费马素性检验是一种素数判定法则,利用随机化算法判断一个数是合数还是可能是素数。
概念
根据费马小定理:如果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.
|