费马素性检验是一种随机化算法,判断一个数是合数还是可能是素数。
根据费马小定理:如果p是素数,1 \le a \le p,那么
a^ \equiv 1 \pmod。
如果我们想知道n是否是素数,我们在中间选取a,看看上面等式是否成立。如果对于数值a等式不成立,那么n是合数。如果有很多的a能够使等式成立,那么我们可以说n 可能是素数,或者伪素数。
在我们检验过程中,有可能我们选取的a都能让等式成立,然而n却是合数。这时等式
a^ \equiv 1 \pmod
被称为Fermat liar。如果我们选取满足下面等式的a
费马素性检验
费马素性检验
a^ \not\equiv 1 \pmod
那么a也就是对于n的合数判定的Fermat witness。
整个算法可以写成是下面两大部:
输入:n需要检验的数;k:参数之一来决定检验需要进行的次数。
输出:当n是合数时,否则可能是素数:
重复k次:
在[1, n − 1]范围内随机选取a
如果an − 1 mod n ≠ 1 那么返回合数
返回可能是素数
1