如何快速筛选质数？费马素性检验和米勒-拉宾测试

如果一个人要买一批瓜，他可能会随机打开几个检查，如果都是熟的，就认为这一批瓜都熟了。在数学上，人们经常使用类似的方法判断一个数是不是质数。质数满足费马小定理，通过随机抽样出的整数进行快速测试，如果一个数通过测试的次数越多，这个数就越有可能是质数。可是，费马素性检验存在致命缺陷，某些特定的数—卡迈克尔数，永远可以通过测试，但是它却不是质数。在现实中，大部分时候，我们会使用类似费马素性检验的方法对事物做出判断，但是我们必须堤防有人刻意向我们展示费马骗子数或者卡迈克尔数，以此误导我们的判断，从中渔利。