python-3.x - Python素性测试程序中的内存错误

Question

def 重复（m，结果，a，s，d）：

check = True
r = 0
while r <= s - 1:
    if result == m - 1:
        check = False
        return check
    result = (result ** 2) % m
    r = r + 1
return check

我需要编写一个素数测试 python 程序来测试非常大的数字，比如至少 100 位数字。上面的代码是 Miller Rabin 确定素数测试重复平方的代码的一部分。对于大量数据，它的工作速度非常慢。我怎样才能加快速度？这是为了一个项目。谢谢！

Answer 1

你的问题可能是(result ** 2) % m，使用它的 3 参数版本pow做同样的事情但更有效，因为算法使用的是模幂x**n，这比先做然后计算它的模要好得多。这样你就可以保证永远不会有一个比你更大的数字m，如果你有的话，(x**n) % m你可以拥有x**n比这大得多的数字m，这可能是你的问题的原因

也不需要check变量，你不使用a. 同样当你从 0 到 s-1 时，更好的使用范围

def repeated(m, result, s, d):
    for r in range(s):
        if result == m - 1:
            return False
        result = pow(result, 2, m )
    return True

现在进行这部分测试

如果

你需要a, d, s,n我就是这样做的

def mr_check(n,a,s,d):
    result = pow(a,d,n)
    if result == 1 :
        return False
    for r in range(s):
        result = pow(result,2,n)
        if result == n-1:
            return False
    return True