如何生成不被互质整数p、q整除的随机整数？单次随机实现

先理清楚核心逻辑：因为p和q互质，0到pq-1这个范围内：

• 总共有 p*q 个数
• 被p整除的有q个，被q整除的有p个，同时被两者整除的只有1个（就是pq本身，如果范围包含它的话）
• 符合要求的数总共是 p*q - p - q + 1 = (p-1)(q-1) 个

所以根本不用循环重试，直接先生成[0, (p-1)(q-1)-1]范围内的随机数，再通过映射转成目标范围内的合法数就行，一次随机数搞定。

两种具体实现方法 #

方法1：分步规避的映射法 #

可以分两步来，先避开被p整除的数，再在结果里去掉被q整除的：

1. 先生成[0, (p-1)*q -1]的随机数x，用你提到的方法转成不被p整除的数：y = x + x//(p-1) + 1（原代码出来的是1到pq之间不被p整除的数，要是想包含0，调整初始随机范围就行）
2. 这时候y已经不被p整除了，但可能被q整除。因为p和q互质，不被p整除的数里，被q整除的有q-1个（就是q、2q…(p-1)q）。可以用下面的逻辑二次调整：
   直接给初始随机数r ∈ [0, (p-1)(q-1)-1]用这个公式：

   a = r // (q-1)
   b = r % (q-1)
   num = a * q + b + 1
   if num % p == 0:
       num += q
   

   原理很简单：先构造出不被q整除的数，再把其中被p整除的那些直接加q跳过——因为p、q互质，加q之后肯定不会被p整除，也不会被q整除，完美符合要求。

方法2：用中国剩余定理直接构造 #

因为p和q互质，每个合法的数n（不被p、q整除），都能对应唯一的(n mod p, n mod q)，其中n mod p在1到p-1之间，n mod q在1到q-1之间。反过来，我们可以先随机生成这两个余数，再用中国剩余定理算出对应的n：

• 先找一个整数m，让m*p % q == 1（因为p、q互质，肯定能找到）
• 然后用公式n = (b - a*m*p) % (p*q)，如果结果是负数就加pq调回正范围

给个Python代码示例：

import random

def extended_gcd(a, b):
    if b == 0:
        return (a, 1, 0)
    g, x, y = extended_gcd(b, a % b)
    return (g, y, x - (a // b) * y)

def get_valid_random(p, q):
    # 随机生成两个合法余数
    a = random.randint(1, p-1)
    b = random.randint(1, q-1)
    # 求m满足m*p ≡1 mod q
    _, m, _ = extended_gcd(p, q)
    m = m % q  # 确保m是正整数
    n = (b - a * m * p) % (p * q)
    return n if n >= 0 else n + p*q

为啥不推荐循环重试？ #

比如p=2、q=3的时候，pq=6，合法数只有2个，重试概率高达2/3，运气差的话要生成好几次随机数，性能拉胯。而上面的映射方法只需要一次随机数，直接转换，效率高多了。

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