3分钟学会费马测试 ﾍ|･∀･|ﾉ*~●

概念

• 费马测试又称为概率性素性测试

• 它的判断是: 某个数是素数的概率大不大 （看，我就说很好理解吧）

素数性质

• 我们就拿5来举例吧。

5   = 素数

4^5 = 1024
3^5 = 243
2^5 = 32
1^5 = 1

• 接下来，再对结果分别求出 mod 5后的余数。

5   = 素数

4^5 = 1024 mod 5 = 4
3^5 = 243  mod 5 = 3
2^5 = 32   mod 5 = 2
1^5 = 1    mod 5 = 1

细心的同学观就会发现。。。

原本的数和余数竟出奇的一致！

费马小定理由此诞生。。。

$$n^p mod p = n$$

实际上不知是5，对于任意素数p，上面的公式都是成立的。

根据是否满足费马小定理来判断一个数是否为素数的方法就是”费马测试”。 (^o^)/

如果p是素数，那么所有比p小的数n都满足费马小定理。

but！

即使所有n都满足条件，p也有可能不是素数！ Σ（ﾟдﾟlll）

因为在极低的条件下会出现所有n都满足条件的合数(非素数的自然数)。

• 比如说 561 可以表示为3 * 11 * 17，所以 561 是合数，不是素数。

这样的合数就叫“卡迈克尔数”(Carmichael numbers)，也叫“绝对伪素数”。

下面按从小到大的顺序列举了一些卡迈克尔数，可以看出这种数非常少。

561      1105     1729
2465     2821     6601
8911     10585    15841
29341    41041    46657
52633    62745    63973

费马小定理、费马测试，你学会了吗？

老规矩！

举手之劳，就点个赞再走呗 ε==(づ′▽`)づ
求支持，跪谢！ (>^ω^<)喵~

注：如果有说错的地方，希望大佬们来指正