朴泊斋

版权声明：转载时请以超链接形式标明文章原始出处和作者信息及本声明
http://damocles.blogbus.com/logs/48736469.html

Proof of Fermat's little theorem(From Algorithms by Dasgupta, C. H. Papadimitriou, and U. V. Vazirani)

用Fermat's little theorem来判断primality

1. 素数都是满足Fermat's little theorem的

2. 满足Fermat's little theorem的不一定是素数

    （1）某些合数只在取特殊的a的时候，满足Fermat's little theorem，如341，这些合数可以通过random取a来做多次判断来剔除

    （2）某些合数就是满足Fermat's little theorem的，这被称为Carmichael Number，最小的数是561，这些数没法剔除，但是很少很少，遇到算你倒霉