sage - Miller-Rabin素性检验-SAGE

Question

我正在尝试在 SAGE 中编写 Miller-Rabin 素数测试。这是我的代码：

def miller(n,k):
i=1
s=(n-1).valuation(2)
t=(n-1)/(2**s)
while(i>0 and i<=k):
    a=randint(3,n-3)
    if gcd(a,n)!=1:
        i=0
    else:
        y=a**t%n
        if y!=1 and y!=n-1:
            j=1
            while(j>0 and j<=s-1 and y!=n-1):
                y=y**2%n
                if y==1:
                    j=0
                else:
                    j=j+1
            if y!=n-1:
                i=0
        if i>0:
            i=i+1
if i==0:
    print "n composite"
else:
    print "n probably prime"

它适用于不太小的数字，但是对于 n=3847982374893247238947238473289472348923784923748723482374832748923748932478239472389478239479273 我得到“3207”至多 947523。我会感谢任何建议:)