선형 합동 생성기

선형 합동 생성기(linear congruential generator, LCG)는 가장 오래되고 단순한 형태의 의사난수 생성기(pseudorandom number generator)로, 다음과 같은 점화식으로 무작위 수열을 생성한다.

정의

LCG는 다음과 같은 점화식을 따른다:

X_n+1 = (aX_n + c) mod m

• X_n: 현재 상태 (난수)
• a: 곱셈 계수 (multiplier)
• c: 증가 값 (increment)
• m: 모듈로 값 (modulus)
• X₀: 초기값 또는 시드(seed)

이 수열에서 각 X_n은 0 이상 m 미만의 정수이며, 정규화된 난수를 생성하려면 X_n / m 값을 사용한다.

조건

좋은 품질의 난수열을 생성하기 위해 다음 조건을 만족해야 한다:

• c ≠ 0일 경우 (혼합형): m, c는 서로소
• a − 1은 m의 모든 소인수로 나누어떨어져야 함
• a − 1은 4의 배수여야 할 수도 있음 (m이 4의 배수일 때)
• 주기(period)는 최대 m이며, 위 조건을 만족할 때 최대 주기를 가짐

예시

• RANDU (역사적으로 유명한 잘못된 LCG)
  • X_n+1 = (65539 × X_n) mod 2³¹
  • 나쁜 품질의 난수로 악명이 높음

• glibc 기본 random():
  • X_n+1 = (1103515245 × X_n + 12345) mod 2³¹

파이썬 예제

다음은 선형 합동 생성기의 간단한 구현 예시이다:

def lcg(a, c, m, seed, n):
    numbers = []
    x = seed
    for _ in range(n):
        x = (a * x + c) % m
        numbers.append(x / m)  # 0 이상 1 미만으로 정규화
    return numbers

# 예시: glibc 파라미터 사용
a = 1103515245
c = 12345
m = 2**31
seed = 42
n = 10

print(lcg(a, c, m, seed, n))

장점

• 구현이 매우 간단하고 빠름
• 정수 연산만으로 계산 가능
• 많은 언어와 시스템에서 기본으로 사용

단점

• 차원 상의 분포가 나쁨 (특히 고차원 공간에서)
• 매개변수 선택이 까다로움
• 보안에 매우 취약 (암호학적 용도에 부적합)

활용

• 간단한 시뮬레이션, 샘플링, 게임 등에서 사용
• 난수 시퀀스의 기초 모델로 소개됨
• 고급 난수 생성기의 참고 구성 요소로 사용되기도 함

같이 보기

• 난수 생성기
• 의사난수
• 시드 (난수 생성)
• Mersenne Twister
• 암호학적 난수 생성기

참고 문헌

• Knuth, D. E. (1997). The Art of Computer Programming, Vol. 2: Seminumerical Algorithms. Addison-Wesley
• Park, S. K., & Miller, K. W. (1988). Random number generators: good ones are hard to find. Communications of the ACM, 31(10), 1192–1201