s_s.m

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

function y=S_S(n,T)
%S_S测试法生成大素数，n：测试数，T：测试次数。
if mod(n,2)==0
    display('n must be a odd number.');
    y=-1;
else
    t=1;
    y=0;
    while(t<=T)
        t=t+1;
        a=ceil((n-1)*rand(1));
        d=gcd(a,n);
        if d~=1
            display('n is not a prime.');
            y=0;
            break;
        else
            p=jacobi_my(a,n);
            p=mod(p,n);
            q=big_mod(a,(n-1)/2,n);
            if p==q
                display('n may be a prime.');
                y=y+1;
            else
                display('n is not a prime.');
                y=0;
                break;
            end
        end
    end
    if y~=0
        y=y/T;
    end
end