Miller-Rabin素性测试Python实现性能基准咨询

我用Python3实现了Miller-Rabin素性测试，但不确定我的机器上这个测试的合理速度标准。用我的代码测试数字 $n = 2^{104}+1$ 耗时不到4秒，不知道这个速度是否理想，求相关性能基准参考。

我的实现代码如下：

def rab_test(N, rounds = 40):
    if N in [2, 3]:
        return True
    if N % 2 == 0:
        return False
    n = N // 2
    t = 1
    while n % 2 == 0:
        n = n // 2
        t += 1
    a = random.randrange(2, N-1)
    u = gmpy2.powmod(a, n, N)
    if u == 1 or N-u == 1:
        return True
    for k in range(1, t):
        u = gmpy2.powmod(u, 2, N)
        if N-u == 1:
            return True
    return False    

首先要指出：你的代码存在一个关键问题——没有实际执行rounds=40轮测试，只跑了1轮，这会大幅提升合数被误判为素数的概率，同时当前的耗时也不是40轮测试的真实耗时。先修正这个问题，再谈性能基准：

性能基准参考 #

你测试的$2^{104}+1$是约3011位的大整数，基于普通消费级CPU（近年Intel i5/i7或同级别AMD处理器）：

• 用gmpy2优化的Miller-Rabin实现，单轮测试耗时通常在50ms-100ms之间；
• 40轮完整测试的正常耗时应该在2-4秒区间，和你当前误跑1轮的耗时刚好匹配——也就是说，如果你修正代码跑满40轮，耗时应该在160秒左右，这才是合理的性能表现；
• 如果不用gmpy2的powmod，纯Python实现的话，3000位数字40轮测试可能需要几十秒甚至数分钟。

代码修正与优化点 #

修正后的完整实现（真正执行指定轮数测试）：

import random
import gmpy2

def rab_test(N, rounds=40):
    if N in [2, 3]:
        return True
    if N % 2 == 0:
        return False
    # 提取 N-1 = d * 2^s，逻辑更清晰
    d = N - 1
    s = 0
    while d % 2 == 0:
        d //= 2
        s += 1
    # 执行rounds轮测试
    for _ in range(rounds):
        a = random.randint(2, N-2)
        x = gmpy2.powmod(a, d, N)
        if x == 1 or x == N-1:
            continue
        # 进行s-1次平方迭代
        for _ in range(s-1):
            x = gmpy2.powmod(x, 2, N)
            if x == N-1:
                break
        else:
            # 迭代结束未找到符合条件的结果，判定为合数
            return False
    # 所有轮测试通过，判定为大概率素数
    return True

额外优化细节：

• 提取N-1 = d*2^s的逻辑更简洁直接，避免原代码中n = N//2的冗余推导；
• 随机数生成用random.randint(2, N-2)，边界逻辑更严谨；
• 严格遵循Miller-Rabin多轮测试的流程，确保结果可靠性。

内容的提问来源于stack exchange，提问作者Lereu