费马小定理通常用来检验一个数是否是素数,是素数的必要非充分条件。
1913 2021-11-05 16:05
费马小定理(Fermat's little theorem)是数论中的一个重要定理,在1636年提出。如果p是一个质数,而整数a不是p的倍数,则有a^(p-1)≡1(mod p)。
数论中a和p互素。所以a肯定不是p的倍数。
费马小定理通常用来检验一个数是否是素数,是素数的必要非充分条件。
然而满足费马小定理检验的数未必是素数,这种合数叫做卡迈克尔数(Carmichael Number),最小的卡迈克尔数是561。
由费马小定理可得,若n为素数,则对任意整数b,且b和n互素,都有bn-1(mod n) ≡1。因此,若存在整数b,使得bn-1(mod n)≡1不成立,则n是一个合数。
利用上述结论,对于给定的整数n,可以设计一个素数判定算法。
1.随机选取整数b,2<=b<=n-2,计算d =bn-1 (mod n)。当d不等于1时,n是合数;当d等于1时,n则很可能是素数,对于本次判断来说,判断错误的概率为1/2。
2.如此重复多次,可以将判断错误的概率降低至期望值以下。
但是,上述方法有缺陷。因为Carmichael数的存在,可导致上述算法给出一个错误的判断。
前3个Carmichael数是561,1105,1729。Carmichael数是非常少的。在1~100000000范围内的整数中,只有255个Carmichael数。
全部评论