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，使用 pow that do the same but more efficiently because the algorithm use is the Modular exponentiation 的 3 个参数版本，这比先做 x**n 然后计算它的模要好得多。这样你就可以保证永远不会有大于 m 的数字，而如果你这样做 (x**n) % m 你可以有 x**n 比 m 大得多，这可能是原因你的问题

也不需要 check 变量并且您不使用 a。另外，当你从 0 到 s-1 时，最好使用 range

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

现在为这部分 test

if

你需要 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

Python 素数测试程序中的内存错误

Memory Error in Python Primality Testing program

python-3.x

primality-test