Miller-Rabin素性测试中从超大范围选取无重复随机元素的问题

当测试极大整数n时，random.sample(range(2, n-1), rounds)会报错，原因是range(2, n-1)的长度为n-3，这个数值超出了C语言ssize_t类型的范围，导致类型转换溢出。

针对这个问题，有两种高效可行的解决方案：

方案一：用集合记录已选元素（基于random模块） #

因为默认测试轮数只有40，远小于大整数n对应的可选底数范围，重复选取的概率极低，用集合去重的方式几乎不会额外增加循环次数，效率足够：

修改后的函数核心部分：

import random
import gmpy2

def miller_rabin(n, rounds = 40):
    if n == 1:
        return False
    if n in [2, 3]:
        return True
    if n % 2 == 0:
        return False
    d = n - 1
    s = 1
    while d % 2 == 0:
        d = d // 2
        s += 1
    chosen = set()
    while len(chosen) < rounds:
        a = random.randrange(2, n-1)
        if a not in chosen:
            chosen.add(a)
            x = gmpy2.powmod(a, d, n)
            for _ in range(s):
                y = gmpy2.powmod(x, 2, n)
                if y == 1 and x != 1 and x != n-1:
                    return False
                x = y
            if y != 1:
                return False
    return True

方案二：使用secrets模块（适合密码学场景） #

如果你的素性测试用于密码学相关场景，推荐使用secrets模块生成更安全的随机数，同样用集合去重：

import secrets
import gmpy2

def miller_rabin(n, rounds = 40):
    if n == 1:
        return False
    if n in [2, 3]:
        return True
    if n % 2 == 0:
        return False
    d = n - 1
    s = 1
    while d % 2 == 0:
        d = d // 2
        s += 1
    chosen = set()
    while len(chosen) < rounds:
        # 生成2到n-1之间的安全随机数
        a = secrets.randbelow(n-2) + 2
        if a not in chosen:
            chosen.add(a)
            x = gmpy2.powmod(a, d, n)
            for _ in range(s):
                y = gmpy2.powmod(x, 2, n)
                if y == 1 and x != 1 and x != n-1:
                    return False
                x = y
            if y != 1:
                return False
    return True

方案说明 #

两种方案都避开了生成超大范围range的操作，而是通过集合记录已选的随机底数，确保每轮测试的底数不重复。由于测试轮数仅为40，对于大整数n来说，重复选取同一底数的概率可以忽略不计，因此不会影响函数的执行效率。

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