메르센 트위스터

메르센 트위스터(Mersenne Twister)는 1997년에 마츠모토 마코토(松本 眞)와 니시무라 다쿠지(西村 拓士)가 개발한 유사난수 생성기이다. 메르센 트위스터는 동일한 저자들이 개발한 TT800 생성기의 개선판으로, 기존 생성기들의 문제점들을 피하면서 매우 질이 좋은 난수를 빠르게 생성할 수 있도록 설계되었다.

메르센 트위스터의 이름은 난수의 반복 주기가 메르센 소수인 데에서 유래했다. 메르센 트위스터는 그 속도와 난수의 품질 때문에 점점 많은 곳에서 채택되고 있으며, 흔히 주기가 $2^{19937}-1$인 MT19937을 사용한다. MT19937과 같으나 생성해 내는 난수가 32비트가 아닌 64비트인 MT19937-64도 쓰이며, 2006년에 동일한 저자들이 발표한 SIMD 기반 메르센 트위스터는 MT19937에 비해 대략 두 배 정도 빠른 것으로 알려져 있다.

난수의 품질에도 불구하고, 메르센 트위스터는 암호학적으로 안전한 유사난수 생성기가 아니다. 즉 난수의 특성(주기, 난수 범위)을 알고 있을 때 유한한 수의 난수(이 경우 624개)만으로 현재 생성기의 상태를 알아 낼 수 있으며, 그 뒤에 나올 난수를 예측해 낼 수 있다. 암호학적으로 안전한 유사난수 생성기를 얻기 위해서는 해시 함수를 사용해야 하지만 난수의 생성 속도가 낮아진다. 또는 블룸 블룸 슙(BBS)과 같이 암호학적으로 안전하게 설계된 생성기를 쓸 수도 있다.

특성

메르센 트위스터 계열의 생성기, 특히 그 중 가장 많이 쓰이는 MT19937은 유사난수 생성기로서 다양한 이점을 가지고 있다.

• 생성해 내는 난수의 주기가 $2^{19937}-1$로 매우 크다. 실용적으로는 거의 대부분의 프로그램이 $2^{19937}-1$개의 고유한 조합을 필요로 하지는 않기 때문에 매우 큰 주기가 실질적으로 큰 도움을 주지는 않는다. (비교를 위해서, $2^{19937}-1$은 대략 $4.315425\times 10^{6001}$이다.)
• 생성된 난수는 623차원까지 동일분포되어 있다. 즉, 난수를 623개까지 짝지어서 623차원 하이퍼큐브에 해당하는 좌표에 점을 찍어도 일관성을 발견할 수 없으며, 따라서 연속된 숫자들 사이의 관계가 매우 낮다. 이 때문에 MT19937은 시뮬레이션에서 자주 사용된다.
• 다이하드 테스트를 비롯한 다양한 확률적 시험을 통과한다.
• 비트 연산만으로 알고리즘의 구현이 가능하기 때문에 매우 빠르다.

반면 MT19937은 다음과 같은 단점도 가지고 있다.

• 생성기의 상태가 비교적 큰 편이다. (적어도 624개의 숫자를 담을 만한 공간이 필요하다.) 이는 임베디드 환경과 같이 매우 적은 메모리만을 사용할 수 있는 환경에서는 큰 단점이 되지만, 대부분의 환경에서는 큰 문제가 되지 않는다.
• 암호학적으로 안전하게 설계되어 있지 않다.
• MT19937의 초기 구현(2002년 이전)의 상태 초기화 루틴은 주어진 초기화 값의 최상위 비트를 상태에 잘 반영하지 않는 문제가 있었다.

외부 링크

• 메르센 트위스터 관련 논문들
• 메르센 트위스터 홈페이지 (C, 포트란 등의 구현 제공)