费马素性检验

费马素性检验是一种質數判定法則,利用随机化算法判断一个数是合数还是可能是素数。

概念

根据费马小定理:如果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都是費馬證人數。

应用

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

参见

参考

  • 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.