메르센 트위스터 문서 원본 보기

{{위키데이터 속성 추적}}
'''메르센 트위스터'''({{lang|en|Mersenne Twister}})는 [[1997년]]에 [[마츠모토 마코토]]({{lang|ja|松本 眞}})와 [[니시무라 다쿠지]]({{lang|ja|西村 拓士}})가 개발한 [[유사난수 생성기]]이다.<ref>[http://doi.acm.org/10.1145/272991.272995 M. Matsumoto & T. Nishimura, "Mersenne twister: a 623-dimensionally equidistributed uniform pseudorandom number generator", ''ACM Trans. Model. Comput. Simul.'' '''8''', 3 (1998).]</ref> 메르센 트위스터는 동일한 저자들이 개발한 [[TT800]] 생성기의 개선판으로, 기존 생성기들의 문제점들을 피하면서 매우 질이 좋은 난수를 빠르게 생성할 수 있도록 설계되었다.

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

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

== 특성 ==

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

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

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

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

== 참조 ==
<references />

== 외부 링크 ==
* [http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/ARTICLES/earticles.html 메르센 트위스터 관련 논문들]
* [https://web.archive.org/web/20070828025507/http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html 메르센 트위스터 홈페이지] ([[C (프로그래밍 언어)|C]], [[포트란]] 등의 구현 제공)

{{전거 통제}}

[[분류:유사난수 생성기]]
[[분류:소수]]