说明: 费马素性检验是一种随机化算法,判断一个数是合数还是可能是素数。 根据费马小定理:如果p是素数,1 \le a \le p,那么 a^ \equiv 1 \pmod。 如果我们想知道n是否是素数,我们在中间选取a,看看上面等式是否成立。如果对于数值a等式不成立,那么n是合数。如果有很多的a能够使等式成立,那么我们可以说n 可能是素数,或者伪素数。 在我们检验过程中,有可能我们选取的a都能让等式成立,然而n却是合数。这时等式 a^ \equiv 1 \pmod 被称为Fermat liar。如果我
<qq_37154060> 上传 | 大小:2kb