對於一個數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必為合數。