역 합동 생성기

역 합동 생성기(inversive congruential generator, ICG)는 비선형적인 유사난수 생성기로, 선형 합동 생성기의 연속된 난수가 가지고 있는 상관 관계를 없애기 위해 합동 곱셈에 대한 역원을 사용하는 알고리즘이다. 역 합동 생성기의 일반식은 다음과 같다.

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

여기서 역 합동 생성기의 각 인자들은 다음과 같은 성질을 만족해야 한다.

• 나눔수 $m$은 소수여야 한다.
• 곱함수 $a$와 더함수 $c$는 0보다 크고 나눔수보다 작아야 한다.
• 초기값 $X_0$은 0보다 크거나 같고 나눔수보다 작아야 한다.

합동 곱셈에 대한 역원 $X_n^{-1}\text{mod}m$은 유클리드 호제법의 확장으로 계산할 수 있다. 또는 페르마 소정리에 따라 $X_n^{m-2}\text{mod}m$을 대신 계산할 수 있다. 이 역원은 나눔수가 소수이기 때문에 $X_n$이 0이 아니면 항상 유일하게 존재하며, $X_n$이 0인 경우 후자와 같이 0을 역원으로 쓸 수 있다.

성질

역 합동 생성기의 난수열 주기는 최대 $m$이며, $x^2-cx-a$가 유한체 ${\mathbb{Z}}_m$ 상에서 원시 다항식일 때 최대 주기를 가진다. 이런 성질을 가지도록 인자를 선택하는 것은 자명하지는 않으나 효율적인 방법이 알려져 있다.

선형 합동 생성기와는 달리, 역 합동 생성기가 생성한 연속된 난수는 좋은 품질을 보이며, 마서글리아 효과와 같이 선형 상관 관계 때문에 나타나는 현상을 보이지 않는다. 또한 역 합동 생성기의 난수열은 $m-2$ 이하의 차원에서 모두 동등분포되어 있다.

그러나 역 합동 생성기는 비교적 느린 연산인 합동 곱셈에 대한 역원을 계산해야 하기 때문에 선형 합동 생성기에 비하여 느리다. 정도의 차이는 있으나 일부 연구(참고 문헌 참고)에 따르면 선형 합동 생성기에 비해 3배 이상의 속도 차이가 나지 않는 것으로 알려져 있다.

변형

역 합동 생성기는 나눔수가 소수가 아닌 경우로 일반화할 수 있다. 특히 컴퓨터 상의 빠른 연산을 위하여 $m$이 2의 거듭제곱인 경우를 고려하면, 다음 조건이 만족될 때 최대 주기인 $\frac{m}{2}$을 얻을 수 있다

$\{\begin{array}{cc}m& =2^e\text{ if }e\ge 3\\ a& \equiv 1(\mathrm{mod}4)\\ b& \equiv 2(\mathrm{mod}4)\end{array}$

명시적인 역 합동 생성기

명시적인 역 합동 생성기(explicit inversive congruential generator, EICG)는 역 합동 생성기와 유사하나 약간 다른 점화식을 사용한다.

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

여기서 0의 역원은 마찬가지로 0으로 정의된다. 이 점화식은 초기 상태만 알고 있어도 임의의 횟수 이후에 생성될 난수를 다음과 같이 쉽게 계산할 수 있다는 장점을 가진다.

$X_{n+1}=(a(n+X_0)+c{)}^{-1}modm$

명시적인 역 합동 생성기는 $a$가 0이 아닐 때 최대 주기인 $m$을 가지며, 일반 역 합동 생성기와 유사한 성질을 가지고 있다. 그러나 점화식의 특성 때문에 난수열을 나눠서 병렬 연산을 할 수 있다는 구분되는 장점이 있다.

같이 보기

• 유사난수
• 선형 합동 생성기

참고 문헌

• Peter Hellekalek, "Inversive pseudorandom number generators: concepts, results and links", Proceedings of the 1995 Winter Simulation Conference, C. Alexopoulos, K. Kang, W.R. Lilegdon, and D. Goldsman (editors), 1995, pp. 255-262.