从巨大范围中选择不重复的随机元素

Question

我有一个关于米勒-拉宾素性测试的实现：

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 = []
    for _ in range(rounds):
        a = random.randrange(2, n-1)
        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

默认情况下，它会进行40轮测试。每次测试时，它会从2到n-1之间随机选择一个数字。

现在我想知道有没有什么快速的方法可以避免重复选择相同的数字。

如果我这样做：

values = random.sample(range(2, n-1), rounds)

我就会遇到错误：Python的整数太大，无法转换为C语言的ssize_t类型。

Answer 1

这个错误的完整追踪信息显示，问题出在随机模块试图获取输入范围的长度。

看起来在获取范围对象长度的过程中，它试图把Python的大整数转换成64位的C语言整数，然后再转换回Python的大整数。_{别问我为什么要做这种奇怪的转换——其实它完全可以一直使用Python的大整数，这样就能避免这个问题。}

有个评论建议使用random.shuffle()，但它也会用到len，所以很可能也会遇到同样的问题。

我不太确定怎么避免这个问题，除非完全重新实现random.sample()。

Answer 2

处理这个问题时，一个重要的因素是 n 的大小。如果 n 小于 2**63，你可以直接使用

random.sample(range(n), rounds)

来获取一个包含所需大小的唯一值的列表。

如果 n 的值比较大，像40这样的小样本数量碰撞的概率几乎为零。不过，如果你想确保绝对安全，最简单的办法就是使用一种拒绝技术。这种方法在Python中使用 set() 非常简单，因为它可以保证元素的唯一性。下面的代码演示了这一点：

import random

def unique_rand_set(n, lower_bd = 2, qty = 40):
    if n < 2**63:
        return random.sample(range(lower_bd, n-1), qty)
    s = set()
    while len(s) < qty:
        s.add(random.randrange(lower_bd, n))
    return s

# The following code just demonstrates usage of the function
n = 1 << 100
my_set = unique_rand_set(n, 5)
for value in my_set:
    print(value)

根据上面的 unique_rand_set() 函数，你需要将

for _ in range(rounds):
    a = random.randrange(2, n-1)
    ...

改成

my_set = unique_rand_set(n)
for a in my_set:
    ...

请注意，由于列表和集合都是可迭代的，所以 for a in my_set: 这个写法无论函数返回哪种类型都能正常工作。

我们从生日问题中知道，直到生成的值接近 O(sqrt(rounds)) 时，碰撞的概率才会显著增加，因此你可以生成数百万个值，而碰撞的可能性非常小。