Linear congruential generator

Question

i want to check whether the selected parameters, a, c and m, will generate full period random number or not. i want to write the code for it. I wrote the code for it but it does not work correctly. the code is

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

this code displays [0, 3, 5, 2, 0, 3, 5, 2, 0, 3, 5, 2, 0, 3]

all three conditions are satisfied but don't know why it is not generating full period random numbers.

Answer 1

The Hull-Dobell theorem specifies three cases in which specific sub-conditions result in a maximal cycle LCG.

• m == prime, c == 0
• m == power of 2, c == 0
• m == power of 2, c ≠ 0

Your parameters don’t qualify for any of the three, since you have a non-zero value of c — excluding cases 1 and 2 — but m is not a power of 2, so you don’t match case 3 either.