第一百四十八章 米勒拉賓素性測試（計算數論）(第1/1頁)
章節報錯
對於一個數n，如果想要判斷它是否為素數，常規的方法為試除法。即，讓n依次除以2到sqrt（n）以內的整數。如果有出現除盡的情況，則為合數。
該方法的時間複雜度為o（sqrt（n））在面對n為長整型的時候有可能超出時間要求。因此普遍採用米勒拉賓演算法進行素性判定。
在此之前介紹一種偽素數判定方法——小費馬定理。
但沒有米勒拉賓素性測試快。
米勒拉賓素性測試是：
判斷一個數p是否為素數
p首先得為大於等於2的正整數才有可能為素數，
首先判奇偶，若為偶數只有2為素數，
若為奇數（這裡可以考慮去掉 3甚至5的倍數），則先求出d。
對於每一個底a，讓d不斷乘以2直到為(p-1)\/2，
在此過程中（包括原本的d與d=(p-1)\/2時的情況），
設t為 a的d次方模p的餘數，
（1）當t=-1時跳出，宣告p有可能為素數
（2）當t=1時，若d為奇數，跳出宣告p有可能為素數，否則跳出宣告p必為合數
（3）當d=(p-1)\/2時跳出，宣告p必為合數。