如果n是素數且(a，n)=1，則a (n-1) = 1 (mod n)。
米勒-拉賓算法是費馬定理的逆向運用；
如果有足夠多的A，(A，n)=1使得A (n-1) = 1 (mod n)成立。
那麽n是壹個質數。
但是它不是壹個完美的算法，
如果以2、3、5、7為基數，那麽在2.5 * 10之內只有3215031751這個數被誤判。
因為a b可以在logB的時間復雜度內完成。
所以Miller-Rabin算法的復雜度O(logn)比naive O(sqrt(n))要快得多。
程序:(可以讓P數組隨機，不壹定要用2，3，5，7做基數)
常數
p:數組[1..4] of integer=(2，3，5，7)；
定義變量
n，I:longint；
f:布爾型；
函數exp(a，b:longint):longint；//計算a b除以n的余數。
定義變量
t:q word；
開始
如果b=0，則退出(1)；
如果b=1那麽退出(a mod n)；
t:=sqr(exp(a，b div 2))mod n；
如果b mod 2=1那麽t:= t * a mod n；
結束；
開始
readln(n)；
f:=真；
for i:=1到4 do
if exp(p[i]，n-1)& lt；& gt那麽1
開始
f:=假；
打破；
結束；
if then writeln(' YES ')else writeln(' NO ')；
結束。
其中需要判斷n為1，2，3，5，7的情況(開頭加個if就行)。
這個程序可以處理所有大於7的質數