求pascal判断素数的米勒拉宾算法

Miller-Rabin算法是基于费马定理的：
如果n为质数，(a,n)=1 那么 a^(n-1)=1 (mod n)

Miller-Rabin算法就是费马定理反向的使用：
如果有足够多的a，(a,n)=1 使a^(n-1)=1 (mod n)都成立
那么n为质数

但是并不是一个完美的算法，
如果以2,3,5,7为底，在2.5*10^13以内只有3215031751这一个数是判断错误的
因为A^B可以在logB的时间复杂度内运算完
所以Miller-Rabin算法的复杂度O(logn)比起朴素O(sqrt(n))快上了非常多

程序：(你可以让p数组随机，不一定要用2,3,5,7为底）
const
p:array[1..4] of integer=(2,3,5,7);
var
n,i:longint;
f:boolean;

function exp(a,b:longint):longint; //计算a^b除以n的余数
var
t:qword;
begin
if b=0 then exit(1);
if b=1 then exit(a mod n);
t:=sqr(exp(a,b div 2)) mod n;
if b mod 2=1 then t:=t*a mod n;
end;

begin
readln(n);
f:=true;
for i:=1 to 4 do
if exp(p[i],n-1)<>1 then
begin
f:=false;
break;
end;
if f then writeln('YES') else writeln('NO');
end.

其中，需要自行判断n为1,2,3,5,7的情况（一开始加个if就行）

这个程序能处理出longint内所有>7的素数

看一下这是不是你说的算法：
对于一个整数n，设n-1=d*2^s(d是奇数)，对于给定的基底a，如果存在a^d=1(mod n)或者对于0<=r经过试验发现，如果以2为底，第一个不符合的数为2047；如果以2、3为底，第一个不符合的数为1373653；如果以2、3、5为底，第一个不符合的数为25326001；如果以2、3、5、7为底，则2^31内的数均符合了。
所以，对于本题，我们直接以2、3、5、7为底进行测试即可。时间复杂度变为了O(NlogN)，比之前的朴素算法有了很多的提高。

我估计第一个回答的人是对的。。。

米勒拉宾算法 是什么？
我只知道暴力和欧拉0.0