费马素性检测，费马小定理

【文件属性】：

文件名称：费马素性检测，费马小定理

文件大小：2KB

文件格式：TXT

更新时间：2021-11-28 10:18:51

c/c++ Fermat

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