費(fèi)馬小定理：如果n是一個(gè)素?cái)?shù)澈魄，a是一個(gè)小于n的正整數(shù)焕参，那么a的n次方與a模n同余
這是一個(gè)充分條件，但是反之是一個(gè)很強(qiáng)的理由晕城，也就是說(shuō)對(duì)于任意的數(shù)n，在1到n之間隨機(jī)的選擇一個(gè)數(shù)窖贤，若(a^n) mod n == a mod n砖顷，那么就可以有很強(qiáng)的理由相信n是一個(gè)素?cái)?shù)，在100 000 000之內(nèi)僅有255個(gè)素?cái)?shù)赃梧，不滿足費(fèi)馬定理的逆命題滤蝠。相比于時(shí)間復(fù)雜度為O（sqrt(n)）樸素檢測(cè)素?cái)?shù)法，在有限次的測(cè)試中能極大概率的判斷一個(gè)素?cái)?shù)是極其有吸引力的授嘀。
( 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 ) ) )
圖片發(fā)自簡(jiǎn)書App
