费马素性检验
概念
根据费马小定理:如果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次:
- 在[1, n − 1]范围内随机选取a
- 如果an − 1 mod n ≠ 1那么返回合数
- 返回可能是素数
若使用模指數運算的快速算法,这个算法的运行时间是O(k×log3n),这里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. . Second. MIT Press; McGraw-Hill. 2001: 889–890. ISBN 0-262-03293-7.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.