Scheme实现费马检查

费马小定理：如果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 ) ) )

Scheme实现费马检查