拉宾米勒素数测试

基础1：费马小定理：当(a,p)=1且P为素数时，有a^{p − 1}modp = 1

基础2：快速幂取模算法（RSA公钥加密算法）

根据费马小定理，有拉宾米勒素数测试法。

对于a^{p − 1}modp = 1

取一组固定的底数a,如{2，3，5，7，11，13}

将待测试的素数P，利用快速幂取模算法，分别与底数a进行测试。

在Maxlongint范围，即2³¹ − 1以下，有一些伪素数（即可以通过拉宾米勒素数测试的合数），目前已知

29341＝13×37×61

3215031751=151*751*23851

在底数取{2,3,5,7,11}可以通过测试。

所以，拉宾米勒素数测试算法是一个不完全准确的算法。

当然，底数a数组取数越多，测试的准确率越高。

const
 
c:array[1..5]of longint=(2,3,5,7,11);
 
function modular_exp(a,p,k:longint):int64;//快速幂取模算法，核心思想为分治
 
var t,ans:int64;
 
begin
 
t:=a;ans:=1;
 
while p>0 do
 
 begin 
 
　if (p and 1=1) then ans:=((ans mod k)*(t mod k)) mod k; 　
 
　t:=((t mod k)*(t mod k)) mod k; 
 
　p:=p shr 1; 
 
　end; 　
 
　exit(ans); 
 
end; 
 
function miller_rabbin(n:longint):boolean;//拉宾米勒测试法
 
var
 
i:longint;
 
begin
 
if n=1 then exit(false);
 
if n in [2,3,5,7,11] then exit(true);
 
for i:=1 to 5 do
 
if modular_exp(c[i],n-1,n)<>1 then exit(false);
 
exit(true);
 
end;

以上程序段来自网络，注释来自编辑者。

算法复杂度：当测试的素数为P时，快速幂取模算法复杂度为O(logP),根据底数a的个数s，整个算法时间复杂度为O(s * logP)

--Kirov 20:47 2010年11月10日 (CST)By TeD