本文介绍在 Miller-Rabin 素性测试等场景中，当需从极大范围（如 [2, n−1]，n 可达 100 位）中随机选取固定数量（如 40 个）互异整数时，规避 random.sample() 溢出错误并保证无重复的实用方案。
本文介绍在 miller-rabin 素性测试等场景中，当需从极大范围（如 `[2, n−1]`，`n` 可达 100 位）中随机选取固定数量（如 40 个）互异整数时，规避 `random.sample()` 溢出错误并保证无重复的实用方案。
在实现 Miller-Rabin 素性测试时，为提升置信度，通常需对多个不同的底数 a ∈ [2, n−1] 进行独立轮次验证。理想情况下，这些底数应互不相同，以避免冗余计算。然而，直接使用 random.sample(range(2, n-1), rounds) 会触发 Python int too large to convert to C ssize_t 错误——这是因为 range() 在 Python 中底层依赖 C 的有符号长整型（ssize_t），而当 n 超过约 2**63（即约 9×10¹⁸）时，range(2, n-1) 无法构造。
解决方案需兼顾正确性（无重复）、效率（低开销）与普适性（支持任意大的 n）。核心思路是根据 n 的量级分治处理：
✅ 小到中等 n（`n 63）**： 可安全使用内置random.sample()`，因其底层优化良好且无内存压力：
import random # 安全适用：n 小于平台最大索引（通常 ~2^63） a_values = random.sample(range(2, n-1), rounds)
✅ 超大 n（如 `n = 2100或 RSA 模数）**： 此时range()不可用，但碰撞概率极低。例如，按生日悖论，从大小为N ≈ 2^100的空间中随机选k = 40个数，发生至少一次重复的概率约为k²/(2N) ≈ 1600 / (2 × 2^100) 简单拒绝采样（rejection sampling）既可靠又高效：
import random
def unique_rand_set(n, lower=2, upper=None, qty=40):
"""
从 [lower, upper) 中安全选取 qty 个唯一随机整数。
自动适配超大 n：小 n 用 random.sample，大 n 用 set 去重。
"""
if upper is None:
upper = n - 1
# 利用 range 可用性判断：n 小则走优化路径
if upper - lower <p>⚠️ <strong>注意事项</strong>： </p>
- set 查重在 Python 中平均时间复杂度为 O(1)，40 次插入的总开销可忽略；
- 无需预先生成全量候选集，内存占用恒定（O(rounds)）；
- 若业务逻辑严格要求确定性顺序（如调试复现），可对结果 sorted(list(bases))，但 Miller-Rabin 中顺序无关；
- 对于极端场景（如 rounds > 10^6），建议改用 Floyd 算法或水库采样变体，但 40 轮完全无需。
综上，通过动态选择 random.sample 或轻量 set 拒绝采样，即可在任意规模输入下稳健、高效地获取无重复随机底数，完美适配密码学级素性检验需求。
