메르센 트위스터 Mersenne Twister

어쩌다 메르센 트위스터라는 걸 알게 되었는데, 이리저리 찾아본 지식이 아까워서-_- 일단 포스팅해 둔다. 이 포스트에 있는 지식은 모두 인터넷에서 얻은 것이고, 본인은 이와 관련하여 전공하지 않았으므로 이 내용은 오류를 포함할 수 있다. ㅋ

 


일전에 Duel_EC_DRBG에 대한 글[1]에서도 잠시 설명했지만, 컴퓨터는 입력값이 결정되면 출력값이 결정되는 장치이므로, 기본적으로는 진정한 의미의 무작위 값을 생성할 수 없다. 그러나 주기가 충분히 길고 값이 비교적 고르게 분포된 수열은 진정한 무작위는 아닐지라도 실용적 수준에서 그럭저럭 쓸만한 값이 될 수 있다. 그런 난수 같아 보이는 수열을 pseudorandom number라 하는데, 메르센 트위스터는 pseudorandom number generator(PRNG)의 한 종류이다. 1997년에 마츠모토 마코토(松本 眞)와 니시무라 타쿠지(西村 拓士)가 제안했다고 한다.

보안이 중요한 경우, 향후 어떤 난수들이 생성될지 해커에게 간파당하면 위험하게 된다. 그러므로 이 경우 난수 생성 알고리즘이 암호학적으로 안전하다는 보장이 필요한데, 메르센 트위스터는 암호학적으로 안전한 난수생성기(CSPRNG)는 아니라고 한다. 그 이유가 뭔지 설명을 해주는 글을 이리저리 찾아봐도 찾지 못했는데, 알고리즘의 제안자 중의 한 명인 마츠모토 선생의 홈페이지의 설명[2]에 따르면 linear recursion으로 생성되는 모든 pseudorandom number는 cryptographically insecure하다고 한다. 본인의 추정으로는, 그러한 알고리즘들은 아무래도 선형계산에 근거하다보니 난수 결과물을 보고 연립방정식을 풀면 난수 생성 베이스가 되는 식의 계수가 모두 도출되지 않을까 하는 짐작이 든다.

어쨌든 그러나 난수에 항상 보안성이 필수적인 것은 아니므로 (게임 캐릭터가 몹을 치는 데미지 라든가 ㅋㅋ), 계산 속도라든지 고르게 값이 나오는 특성이 더 중요할 수도 있다. 예를 들어 0부터 1023까지 true random하게 정수열을 생성하는 장치가 있다면, 이를 mod 100으로 처리할 경우 0부터 23까지의 숫자가 24부터 99까지의 숫자보다 약간 더 자주 발생하게 되어 고르지 않게 된다. 컴퓨터 시대의 초창기에는 Middle-square method를 썼다고 하는데, 이 경우 난수의 품질이 상당히 좋지 않다고 한다. (예를 들어, 중간에 영을 많이 포함하는 수가 나오면 이후로 영이 많아진다.) 메르센 트위스터의 경우 위키피디아의 설명에 따르면 고속으로 고품질의 난수를 생성해 내는 최초의 알고리즘이어서 꽤 실용적이었던 모양이다. 근데 왜 주기가 그렇게 길고 고르게 분포되는지는 마츠모토 선생의 원래 논문[3]에 있는 듯 한데, 잘 이해가 안 돼서 접었다-_-

이 알고리즘의 이름의 유래에 관해서는 마츠모토 선생의 홈페이지에 짧게 설명[4]이 있는데, 조금 웃겨서-_- 번역해본다.

MTは、最初は「Primitive Twisted Generalized Feedback Shift Register Sequence」 という名前でした。(歴史的な理由による。)
眞:Knuthさんが手紙で「舌を噛みそうな名前だ」ってさ。
拓:……。

数日後
眞:ねえねえ、Mersenne Twisterっていうのはどう?使っているのは、 メルセンヌ素数だし、 この前身がTwisted GFSRだというのもあらわしてるし。
拓:はあ。
眞:何かジェットコースターみたいで速そうだし、覚えやすいし呼びやすいし。 しかもね、秘密だけど、作った人のinitialが隠されているんだよ。
拓:……。
眞:MTで行こうよ、MTで。
拓:はあ、いいんじゃないですか。

後日、Knuthさんから「いい名前だと思う」とのありがたいお言葉を 頂きました。


MT는 처음에 「Primitive Twisted Generalized Feedback Shift Register Sequence」 라는 이름이었습니다. (역사적인 이유에 따름)
마코토 : Knuth씨가 편지에 「혀가 꼬일 이름이군요」라는군.
타쿠지 : ……

수 일 후
마코토 : 이봐 이봐, Mersenne Twister는 어때? 메르센 소수을 사용하기도 하고, Twisted GFSR의 뒤를 잇는 것이기도 하고.
타쿠지 : 음.
마코토 : 뭔가 제트코스터를 타듯이 빠르다는 느낌이고, 기억하기 쉽고 부르기 쉽구만. 그런데 이건 비밀이지만, 만든 사람의 이니셜이 숨어있다고.
타쿠지 : …..
마코토 : MT로 가자고. MT로.
타쿠지 : 음, 괜찮지 않겠습니까.

후에 Knuth씨가 고맙게도 「좋은 이름이라 생각합니다」라고 말을 하셨습니다.

ㅋㅋㅋㅋ 작명 센스 인정한다. ㅋㅋㅋ

 


서론이 길었는데, 그럼 과연 메르센 트위스터는 어떻게 값을 생성하는가?

스칼라가 binary field(즉 0과 1의 두 원소로 이루어진 field)인 벡터들로 이루어진 벡터열을 귀납적으로 생성한다. 즉, n개의 벡터로 된 초항 (seed value라고도 한다) x_1 ,x_2, \cdots , x_n이 주어진 벡터열 \left\{x_k \right\}을 생각하자. 벡터의 dimension은 컴퓨터의 OS가 32비트이면 32, 64비트이면 64이다. 이 벡터의 dimension을 w라 하자. m은 1과 n사이의 자연수라고 하자.

벡터열의 각 항은 다음과 같은 bitwise 연산을 이용한 점화식으로 계산한다.

\displaystyle x_{k+n} = x_{k+m} \oplus (x_k^u \mid x_{k+1}^l )A     (k=0, 1, 2, …)

여기서 r은 벡터를 잘라내는 위치다. 즉, x_k^u는 벡터 x_k의 앞부분 w-r 비트를 의미하고 x_{k+1}^l은 벡터 x_{k+1}의 뒷부분 r비트를 의미한다. 세로줄 | 은 잘라낸 w-r비트와 r비트를 이어붙이라는(concatenation) 뜻이다. 위키피디아에서는 이것이 or 연산이라고 설명되어 있는데, 이는 잘못된 설명이다.

또, \oplus는 xor 연산이고(binary field의 addition과 xor은 정확히 동일하다!), A는 상수 행렬로서 xA는 벡터 x를 1 \times w의 행렬로 보는 행렬곱이다. 행렬 A의 내용은 다음과 같다.

\displaystyle A = \begin{pmatrix} 0 & I_{w - 1} \\ a_{w-1} & (a_{w - 2}, \ldots , a_0) \end{pmatrix}

여기서 0은 이미 짐작했듯이, entry가 모두 영인 (w-1) \times 1 행렬이고 I_{w - 1}(w-1) \times (w-1) 크기의 identity matrix이다. 각 a들은 0 또는 1의 상수가 된다.

이 notation은 대부분 마츠모토 선생의 원 논문[3]을 그대로 따른 것인데, 좀 헷갈리게 써놨다. 위 점화식에서 xor 연산과 행렬 곱 중에서 어느 쪽이 먼저 연산되는지 애매한데, 원 논문[3,p6]을 보니 행렬 곱이 먼저 계산되어야 한다.

이 점화식을 코드로 실제 구현할 때는 다행히도 행렬 곱을 할 필요가 없다. 어떤 벡터 x와 위 행렬 A의 곱은 다음 결과와 동일하다.

\displaystyle \boldsymbol{x}A = \begin{cases}\boldsymbol{x} \gg 1 & (x_0 = 0) \\(\boldsymbol{x} \gg 1) \oplus \boldsymbol{a} & (x_0 = 1)\end{cases}

여기서 이 사람들이 notation을 헷갈리게 해 놓았는데, 벡터 x의 entry에서 가장 우측의 coordinate가 x_0 임에 유의하자. 꺾은 괄호 두 개는 우측으로의 비트 이동을 뜻하고, 벡터 a는 행렬 A의 마지막 행(최하단부)을 그대로 벡터로 만든 것이다. 똑같은지 실제로 행렬 곱을 해 보시라! ㅋ

한편 값이 좀 더 고르게 되기 위해서 invertable matrix T를 이용하여 conjugation (T^{-1}AT)을 사용한다고 한다. 근데 이게 왜 값이 고르게 되는지는 잘 모르겠다. ㅋ 실력 부족이다.

여하간 따라서 이 과정을 실제로 구현하기 위해서는 상수들의 결정이 필요한데, 위키피디아에는 32비트와 64비트에서 MT19937에 해당하는 값들 소개되어 있다. 위키피디아에 따르면 32비트에서는 벡터 a의 값으로 0x9908B0DF 를, 64비트에서는 0xB5026F5AA96619E9 를 쓴다고 한다.

 


[1] 내 백과사전 내가 이해한 Dual_EC_DRBG 백도어 2014년 1월 3일
[2] http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/efaq.html
[3] M. Matsumoto and T. Nishimura, “Mersenne Twister: A 623-dimensionally equidistributed uniform pseudorandom number generator”, ACM Trans. on Modeling and Computer Simulation Vol. 8, No. 1, January pp.3-30 (1998) DOI:10.1145/272991.272995
[4] http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/name.html

6 thoughts on “메르센 트위스터 Mersenne Twister

  1. 97년이니까 발표된지 20년이 다 돼가는데 여전히 메르센 트위스터보다 딱히 더 나은 유사난수 알고리즘이 없다더군요.
    더 나은건 고사하고 레거시 때문인지 아직도 많은 언어의 기본 생성기가 무진장 후진 알고리즘을 쓰고 있고 사고도 종종 터진다고…

    • 음 그 정도까진 아닙니다. 최근 웹 브라우저들은 XorShift128+로 거의 대동단결한 상태이고요(파폭이 MT19937 쓰다가 옮겨 탔고, 크롬이 MWC1616을 쓰다가 피를 보고 최근에 옮겨 탔습니다), PCG http://www.pcg-random.org/ 같은 것도 있지요. 아니면 Rust 같이 아예 기본 난수 생성기가 cryptographically secure한 케이스(ISAAC)도 있습니다.

      메르센 트위스터의 주된 문제는 상태가 지나치게 크고(주기가 2^19937-1이니까 말 그대로 최소 19937비트 = 2.5KB의 상태가 필요) 생각보다 연산이 많이 필요하다는 데 있습니다. 수학 시뮬레이션 같이 equidistribution이 매우 중요한 케이스가 아니면 2^19937 – 1 같은 무지막지한 공간이 필요하진 않은게 사실입니다. (XorShift128+의 경우 equidistribution을 제공하지 않고, WELL 같은 것들이 MT19937과 비슷하거나 더 나은 성질을 제공하는 대신 XorShift 계열만치 빠르진 않은 걸로 압니다.)

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Google+ photo

Google+의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

%s에 연결하는 중