线性同余发生器

Question

我想检查所选参数a、c和m是否会生成全周期随机数。我想为其编写代码。我为其编写了代码，但它无法正常工作。 代码是

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))

此代码显示 [0, 3, 5, 2, 0, 3, 5, 2, 0, 3, 5, 2, 0, 3]

所有三个条件都满足，但不知道为什么它没有生成全周期随机数。

Answer 1

赫尔-多贝尔定理指定了特定条件导致全循环 LCG 的三种情况。您的参数不符合这三个参数中的任何一个，因为您有一个非零值 c

 — 不包括情况 1 和 2 — 但 

m

 不是 2 的幂，所以您不匹配情况 3要么。