费马小定理：如果n是一个素数，a是一个小于n的正整数，那么a的n次方与a模n同余
这是一个充分条件，但是反之是一个很强的理由，也就是说对于任意的数n，在1到n之间随机的选择一个数，若(a^n) mod n == a mod n，那么就可以有很强的理由相信n是一个素数，在100 000 000之内仅有255个素数，不满足费马定理的逆命题。相比于时间复杂度为O（sqrt(n)）朴素检测素数法，在有限次的测试中能极大概率的判断一个素数是极其有吸引力的。
( define (expmod base exp m )
( cond ( ( = exp 0 ) 1 )
( ( even? exp )
( remainder (square ( expmod base ( / exp 2 ) m ) )
m ) )
( else
(remainder ( * base (expmod base ( - exp 1 ) m ) ) m ) ) ) )
( define ( fermat-test n )
( define ( try-it a )
( = ( expmod a n n ) a ) )
( try-it ( + 1 ( random ( - n 1 ) ) ) ) )
( define ( fast-prime? n times )
( cond ( ( = times 0 ) true )
( ( fermat-test n )
( fast-prime? n ( - times 1 ) ) )
( else false ) ) )
图片发自简书App
