費(fèi)馬小定理：對(duì)于素?cái)?shù)p和任意整數(shù)a决侈，有ap ≡ a(mod p)（同余）词渤。反過來牵舱，滿足ap ≡ a(mod p)，p也幾乎一定是素?cái)?shù)缺虐。
偽素?cái)?shù)：如果n是一個(gè)正整數(shù)芜壁，如果存在和n互素的正整數(shù)a滿足 an-1 ≡ 1(mod n)，我們說n是基于a的偽素?cái)?shù)志笼。如果一個(gè)數(shù)是偽素?cái)?shù)沿盅，那么它幾乎肯定是素?cái)?shù)。
Miller-Rabin測(cè)試：不斷選取不超過n-1的基b(s次)纫溃，計(jì)算是否每次都有bn-1 ≡ 1(mod n)腰涧，若每次都成立則n是素?cái)?shù)，否則為合數(shù)紊浩。
Function Miller-Rabin (n : longint) :boolean;
begin
for i := 1 to s do
begin
a := random(n - 2) + 2;
if mod_exp(a, n-1, n) <> 1 then return false;
end;
return true;
end;
