线性同余生成器(LCG)参数校验代码异常：无法生成全周期序列

我编写了一段校验LCG参数a、c、m是否能生成全周期随机数的代码，但运行结果不符合预期。输入参数seed=0、a=5、c=3、m=13时，代码判定所有全周期条件均满足，却输出重复序列[0, 3, 5, 2, 0, 3, 5, 2, 0, 3, 5, 2, 0, 3]，不知道问题出在哪里。

原代码 #

def gcd(small, large):
    if(large < small):
      temp = large
      large = small
      small = temp

    for i in range(small, 0, -1):
        
        if large % i == 0 and small % i == 0:
            return i

# m and c must be co-prime
def relative_prime_condition(c, m):
    if gcd(c,m) == 1:
        return True
    return False

def is_prime(number):
    for i in range(2, int(number/2) + 1):
        if number % i == 0:
            return False
    return True
    
# a-1 must divide all the prime factors of m
def prime_factor_condition(a, m):
    for i in range(2, int(m/2) + 1):
        if is_prime(i) and m % i == 0 and (a-1) % i != 0:
            return False
    return True

# if m divides 4, then a-1 must divide 4    
def num4_condition(a, m):
    if m % 4 == 0 and (a-1) % 4 != 0:
        return False
    return True
    
def LCG(seed, a, c, m):
    random_numbers = [seed]
    
    if relative_prime_condition(c,m) and prime_factor_condition(a,m) and num4_condition(c,m):
        for i in range(1, m+1):
            random_numbers.append((a * random_numbers[i-1] + c) % m)
    
    else:
        print("These Parameters are not able to generate the random numbers")
        for i in range(1, 5):
            random_numbers.append((a * random_numbers[i-1] + c) % m)
    
    return random_numbers

print(LCG(seed=0, a=5, c=3, m=13))

问题定位 #

代码存在两个核心错误：

1. 参数传递错误：在LCG函数的条件判断中，错误地将num4_condition(c,m)作为判断条件，而该函数的正确参数应为num4_condition(a,m)，导致该条件被误判为满足。
2. 质因数检查逻辑缺失：prime_factor_condition函数的循环范围仅到int(m/2)+1，当m本身是质数（如示例中的13）时，无法检测到m自身这个质因数。示例中a-1=4无法被13整除，本应不满足全周期条件，但代码未检测到这一点，错误判定条件满足。

修复方案 #

修正后的代码 #

def gcd(small, large):
    if large < small:
        temp = large
        large = small
        small = temp

    for i in range(small, 0, -1):
        if large % i == 0 and small % i == 0:
            return i

# m和c必须互质
def relative_prime_condition(c, m):
    return gcd(c, m) == 1

def is_prime(number):
    if number <= 1:
        return False
    if number == 2:
        return True
    if number % 2 == 0:
        return False
    for i in range(3, int(number**0.5) + 1, 2):
        if number % i == 0:
            return False
    return True

# 获取m的所有不同质因数
def get_prime_factors(m):
    factors = set()
    if m % 2 == 0:
        factors.add(2)
        while m % 2 == 0:
            m = m // 2
    i = 3
    while i * i <= m:
        if m % i == 0:
            factors.add(i)
            while m % i == 0:
                m = m // i
        i += 2
    if m > 2:
        factors.add(m)
    return factors

# 对于m的每个质因数p，a-1必须能被p整除
def prime_factor_condition(a, m):
    factors = get_prime_factors(m)
    for p in factors:
        if (a - 1) % p != 0:
            return False
    return True

# 如果m能被4整除，那么a-1必须能被4整除
def num4_condition(a, m):
    if m % 4 == 0 and (a - 1) % 4 != 0:
        return False
    return True

def LCG(seed, a, c, m):
    random_numbers = [seed]
    
    # 修正参数传递错误
    if relative_prime_condition(c, m) and prime_factor_condition(a, m) and num4_condition(a, m):
        # 初始已有seed，生成m-1个新数即可得到全周期m个数
        for i in range(1, m):
            next_num = (a * random_numbers[i-1] + c) % m
            random_numbers.append(next_num)
    else:
        print("这些参数无法生成全周期随机数")
        for i in range(1, 5):
            next_num = (a * random_numbers[i-1] + c) % m
            random_numbers.append(next_num)
    
    return random_numbers

print(LCG(seed=0, a=5, c=3, m=13))

修复后效果 #

输入seed=0、a=5、c=3、m=13时，代码会输出提示“这些参数无法生成全周期随机数”，并返回短序列[0, 3, 5, 2, 0]，符合实际条件判定结果。

若使用满足全周期条件的参数（如a=4、c=1、m=13），则会生成包含13个不同数值的全周期序列。

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