费马素性检验

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

概念

根据 费马小定理:如果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