第一百四十八章 米勒拉賓素性測試（計(jì)算數(shù)論）

　　對于一個(gè)數(shù)n，如果想要判斷它是否為素?cái)?shù)，常規(guī)的方法為試除法。即，讓n依次除以2到sqrt（n）以內(nèi)的整數(shù)。如果有出現(xiàn)除盡的情況，則為合數(shù)。

　　該方法的時(shí)間復(fù)雜度為O（sqrt（n））在面對n為長整型的時(shí)候有可能超出時(shí)間要求。因此普遍采用米勒拉賓算法進(jìn)行素性判定。

　　在此之前介紹一種偽素?cái)?shù)判定方法——小費(fèi)馬定理。

　　但沒有米勒拉賓素性測試快。

　　米勒拉賓素性測試是：

　　判斷一個(gè)數(shù)p是否為素?cái)?shù)

　　p首先得為大于等于2的正整數(shù)才有可能為素?cái)?shù)，

　　首先判奇偶，若為偶數(shù)只有2為素?cái)?shù)，

　　若為奇數(shù)（這里可以考慮去掉 3甚至5的倍數(shù)），則先求出d。

　　對于每一個(gè)底a，讓d不斷乘以2直到為(p-1)/2，

　　在此過程中（包括原本的d與d=(p-1)/2時(shí)的情況），

　　設(shè)t為 a的d次方模p的余數(shù)，

　?。?）當(dāng)t=-1時(shí)跳出，聲明p有可能為素?cái)?shù)

　?。?）當(dāng)t=1時(shí)，若d為奇數(shù)，跳出聲明p有可能為素?cái)?shù)，否則跳出聲明p必為合數(shù)

　　（3）當(dāng)d=(p-1)/2時(shí)跳出，聲明p必為合數(shù)。