선형 합동 생성기

선형 합동 생성기(Linear congruential generator, LCG)는 널리 알려진 유사난수 생성기이다. 선형 합동 생성기는 다음 재귀 관계로 정의된 순열 $X_i$을 반환한다.

$X_{n+1}=(a{X}_n+c)modm$

따라서 선형 합동 생성기는 다음과 같은 인자들로 유일하게 결정된다.

• 0 < $m$ (나눔수)
• 0 < $a$ (곱함수) < $m$
• 0 ≤ $c$ (더함수) < $m$
• 0 ≤ $X_0$ (초기값) < $m$

선형 합동 생성기의 상태는 바로 이전에 생성된 난수이며, 이 난수는 최대 $m$가지 경우가 있으므로 난수의 주기는 최대 $m$임이 자명하다. 하지만 대부분의 경우 이 주기는 훨씬 짧으며, 최대 주기를 갖기 위한 필요충분조건은 다음과 같다.

1. $c$와 $m$이 서로소여야 한다.
2. $a-1$이 $m$의 모든 소인수로 나눠져야 한다.
3. $m$이 4의 배수일 경우, $a-1$도 4의 배수여야 한다.

선형 합동 생성기는 그 인자들과 마지막으로 생성된 난수를 알면 그 뒤에 만들어질 모든 난수를 예측할 수 있기 때문에 암호학적으로 안전한 유사난수 생성기가 아니다. 또한 선형 합동 생성기가 생성해 내는 난수의 질은 그 인자에 따라 극적으로 달라지며, 인자에 따라서는 적절치 못한 초기값 때문에 문제가 생기기도 한다. (예를 들어 $c=X_0=0$인 경우)

예제

《Numerical Recipes in C》는 다음 형태의 선형 합동 생성기를 권장했다.

$X_{n+1}=(1664525X_n+1013904223)mod{2}^{32}$

볼랜드 터보 C에 포함된 rand() 함수는 다음 식을 사용하되, 상위 16비트만을 반환했다.

$X_{n+1}=(22695477X_n+1)mod{2}^{32}$

매우 나쁜 난수열을 생성해 내는 것으로 알려진 RANDU 루틴은 다음 수식을 사용한다.

$X_{n+1}=(65539X_n)mod{2}^{31}$

일반적으로 컴퓨터에서는 나눗셈 및 나머지 연산이 매우 느리기 때문에 $m$이 $2^{16}$이나 $2^{32}$ 같이 정수의 크기에 맞는 나눔수를 흔히 사용한다. 자주 사용되는 다음 생성기는 그렇지 않은 한 예이다.

$X_{n+1}=(279470273X_n)mod(2^{32}-5)$

위 생성기는 C99 코드로 다음과 같이 표현할 수 있다.

#include <stdint.h>

uint32_t lcg_rand(uint32_t a)
{
    return ((uint64_t)a * 279470273) % 4294967291;
}

특성

파일:Lcg 3d.gif

선형 합동 생성기로부터 만들어 낸 3차원 좌표에 점을 찍으면 여러 개의 평면 상에 나타남을 알 수 있다.

선형 합동 생성기는, 비록 최대 주기를 가지도록 인자를 선택했더라도 아주 좋은 품질의 난수열을 생성해 내지 못한다. 예를 들어 선형 합동 생성기가 만드는 연속된 난수들 사이에 상당한 상관 관계가 존재하기 때문에 몬테 카를로 시뮬레이션에 적합하지 않으며, 마지막으로 생성된 난수를 알면 그 뒤에 만들어질 난수를 모두 예측할 수 있기 때문에 암호학적인 목적으로도 사용할 수 없다

특정한 경우 선형 합동 생성기의 사용이 사실상 불가능할 수도 있다. 만약 선형 합동 생성기가 만들어 내는 숫자를 $n$개씩 짝을 지어 $n$차원 공간 상에 점을 찍으면, 마서글리아 효과에 따라 그 점들은 최대 $m^{\frac{1}{n}}$개의 초평면 상에 위치하게 된다. 또한 $m$이 2의 거듭제곱일 경우 생성된 난수열의 하위 비트들은 상위 비트들에 비해 훨씬 강한 상관관계를 나타낸다. (예를 들어 최하위 비트는 0, 1, 0, 1 순으로 반복될 것이다.) 때문에 많은 선형 합동 생성기 구현에서는 하위 비트를 버리고 상위 비트만을 반환하곤 한다

선형 합동 생성기를 쓸 수 있는 대부분의 환경에서는 메르센 트위스터와 같은 생성기를 쓰는 것이 난수의 질이나 속도 면에서 더 좋다. 반면 선형 합동 생성기는 이들 생성기가 적용되기 힘든 환경에서 유리한데, 예를 들어 메르센 트위스터는 2킬로바이트 정도의 메모리를 요구하지만 많은 임베디드 환경에서는 이보다 적은 메모리만을 가지고 있는 경우가 많다. 또한 상관 관계에 대한 고려가 필요하지 않은 경우에도 선형 합동 생성기가 사용되는데, 한 예로 대부분의 메르센 트위스터 구현에서는 의사 난수 생성기를 사용해서 초기값으로부터 더 큰 초기화 벡터를 만들어 낸다. (이 경우 후에 상태가 뒤섞이면서 초기의 상관 관계가 사라지게 된다.)

참조

• Stephen K. Park and Keith W. Miller, Random Number Generators: Good Ones Are Hard To Find, Communications of the ACM, 31(10):1192-1201, 1988
• D. E. Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89684-2. Section 3.2.1: The Linear Congruential Method, pp.10–26.

같이 보기

• 역 합동 생성기