s_s2.m

solovay-strassen素性测试法的matlab实现

function p=S_S2(n,T)
%测试n是素数的概率
if mod(n,2)==0
    display('n must be a odd number.');
    p=-1;
else
    t=1;
    k=0;
    while(t<=T)
        t=t+1;
        a=ceil((n-1)*rand(1));
        d=gcd(a,n);
        if d==1
            p=jacobi_my(a,n);
            q=big_mod(a,(n-1)/2,n);
            if mod(p,n)==q
                k=k+1;
            end
        end
    end
    display('the probability that n is a prime is :');
    p=k/T;
end