메르센 트위스터

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

메르센 트위스터(Mersenne Twister)는 1997년마츠모토 마코토(松本 眞)와 니시무라 다쿠지(西村 拓士)가 개발한 유사난수 생성기이다.[1] 메르센 트위스터는 동일한 저자들이 개발한 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년 이전)의 상태 초기화 루틴은 주어진 초기화 값의 최상위 비트를 상태에 잘 반영하지 않는 문제가 있었다.

참조[편집]

  1. M. Matsumoto & T. Nishimura, "Mersenne twister: a 623-dimensionally equidistributed uniform pseudorandom number generator", ACM Trans. Model. Comput. Simul. 8, 3 (1998).

바깥 고리[편집]