메르센 트위스터

소프트웨어 통계 마지막 수정: 2026-08-03 04:51:33

1. 개요[편집]

메르센 트위스터 Mersenne Twister (MT19937)
개발	마쓰모토 마코토, 니시무라 다쿠지 (1997)
주기	2¹⁹⁹³⁷ − 1 (메르센 소수)
균등분포 차원	623차원 (32비트 정밀도)
내부 상태	624 × 32비트 ≈ 2.5 KB
암호학적 안전성	없음 (출력 624개면 상태 복원)
후속·대안	SFMT/dSFMT, PCG, xoshiro, Philox

20년 넘게 모든 언어의 기본 난수 생성기였던 물건. 그리고 지금은 “왜 아직도 이걸 쓰냐”는 소리를 듣는 물건.

메르센 트위스터(Mersenne Twister)는 1997년 마쓰모토 마코토와 니시무라 다쿠지가 발표한 의사난수 생성기로, 대표 변형인 MT19937은 주기 $2^{19937}-1$ 과 623차원 균등분포를 갖는다. 이름의 “메르센”은 주기의 지수 19937이 메르센 소수 지수라는 데서 왔고, “트위스터”는 되먹임 시프트 레지스터에 비틀림(twist) 변환을 넣은 구조에서 왔다.

발표 직후부터 C++11 표준 라이브러리, 파이썬 random, R, MATLAB, 초기 NumPy 등 거의 모든 주류 환경의 기본값이 되었고, 지난 사반세기 동안 나온 몬테카를로 방법 계산의 상당수가 이 생성기 위에서 돌았다. 난수 생성기 일반론과 품질 판정 기준은 난수 생성기 문서에, 균등난수를 목표 분포로 바꾸는 변환은 역변환 표본추출·박스-뮐러 변환·기각표본추출에 있다. 이 문서는 MT 자체의 구조와 한계, 그리고 왜 후계자들이 등장했는가를 다룬다.

2. 구조[편집]

MT는 $\mathbb{F}_2$ 위의 선형 점화식으로 정의되는 TGFSR(twisted generalized feedback shift register) 계열이다. MT19937의 파라미터는 $n = 624$ , $m = 397$ , $r = 31$ 이고, 상태 워드 $x_k$ 에 대한 점화식은

x_{k+n} = x_{k+m} \oplus \left( x_k^{u} \,\Vert\, x_{k+1}^{l} \right) A

이다. $x_k^{u}$ 는 $x_k$ 의 상위 1비트, $x_{k+1}^{l}$ 은 $x_{k+1}$ 의 하위 31비트이며, 둘을 이어 붙인 32비트 워드에 유리 정규형 행렬 $A$ 를 곱한다. $A$ 곱셈은 실제로는 1비트 시프트와 상수 0x9908B0DF와의 조건부 XOR 한 번이라 곱셈기가 전혀 필요 없다. 이 “비틀림”이 순수 GFSR의 나쁜 격자 구조를 깨뜨리는 핵심 장치다.

점화식만으로는 출력의 하위 비트 균등성이 떨어지므로, 꺼낸 워드에 tempering이라 부르는 가역 선형 변환을 한 번 더 건다. 시프트-마스크-XOR 네 단계로 이루어진 이 변환은 전단사(bijective)이며, 바로 그 가역성이 뒤에 나올 보안 취약점의 원인이 된다.

MT가 당대에 압도적이었던 이유는 성능이 아니라 증명된 성질이었다. 623차원 균등분포는 “연속한 623개 출력을 좌표로 삼아 만든 점들이 32비트 정밀도에서 초입방체를 고르게 채운다”는 뜻이고, 이는 실험이 아니라 수학적으로 확립된 사실이다. 당시 흔했던 선형 합동 생성기가 고차원에서 얇은 초평면 위에만 점을 찍는 문제(마살리아 격자 구조)로 악명 높았던 것과 대비된다.

3. 왜 표준이 되었나[편집]

주기가 사실상 무한. $2^{19937}$ 은 우주의 원자 수 따위와 비교하는 것이 무의미한 크기라, 주기 소진을 걱정할 필요가 없다.
고차원 균등성이 증명되어 있음. 대부분의 통계 검정을 무난히 통과하고, 통과하는 이유가 우연이 아니다.
속도가 충분히 빠름. 시프트·XOR·마스크만 쓰므로 나눗셈이나 모듈러 연산이 없다.
레퍼런스 구현이 공개되어 있고 이식이 쉬움. 언어·플랫폼 간 재현성 확보가 쉬웠다.

특히 재현성은 과학 계산에서 과소평가된 미덕이다. 같은 시드로 어디서 돌려도 같은 수열이 나온다는 보장 덕분에 이징 모형이나 담금질 모사 실험의 결과를 다른 그룹이 그대로 재현할 수 있었다.

4. 약점 — 정직하게[편집]

4.1. 암호학적으로 전혀 안전하지 않다[편집]

MT는 선형 생성기다. tempering이 가역이므로 연속한 624개의 32비트 출력만 관측하면 tempering을 역으로 풀어 내부 상태 전체를 복원할 수 있고, 그 뒤로는 과거와 미래의 모든 출력을 그대로 계산해 낸다. 이건 구현 버그가 아니라 설계상 당연한 귀결이다. 시뮬레이션용 생성기를 토큰·세션 키·셔플 검증에 갖다 쓴 사고가 반복적으로 터진 이유가 이것이다.¹

4.2. 0이 많은 초기 상태에서 회복이 느리다[편집]

점화식이 XOR 기반이라 상태 워드 대부분이 0이면 새 워드도 0이 되기 쉽다. 이 zero-excess 상태에 빠지면 정상적인 통계 성질을 회복하는 데 최대 수십만 회의 출력이 필요할 수 있다. seed(0), seed(1) 처럼 작은 정수로 초기화하는 관행이 위험한 것도 이 때문인데, 그래서 표준 구현은 크누스식 곱셈 점화로 상태를 채우는 초기화 루틴(그리고 배열 시드용 init_by_array)을 함께 제공한다.

4.3. 상태가 크다[편집]

624워드 = 약 2.5 KB. L1 캐시가 귀한 요즘 기준으로는 부담스러운 크기이며, 스레드마다 독립 스트림을 두는 병렬 계산에서는 이 비용이 스레드 수만큼 곱해진다. 상태가 64비트 두어 개인 최신 생성기들과 비교하면 캐시 지역성 면에서 확실히 불리하다.

4.4. 선형성이 검정에 잡힌다[편집]

$\mathbb{F}_2$ 선형 구조 때문에 TestU01 스위트의 BigCrush 중 선형복잡도·행렬 계수(matrix rank) 계열 검정을 체계적으로 통과하지 못한다. 이 실패가 실제 물리 시뮬레이션 결과를 얼마나 오염시키는지는 문제에 따라 다르지만, 비트 단위 연산으로 상태를 만드는 계산(예: 스핀 배열을 비트마스크로 다루는 코드)에서는 실질적인 편향으로 나타날 수 있다.

5. 후속 세대와 현대의 선택[편집]

MT 진영 자체의 개선판이 SFMT(SIMD-oriented Fast Mersenne Twister, 2006)다. 128비트 SIMD 워드 단위로 재설계해 속도를 크게 끌어올리고 zero-excess 회복 속도도 개선했으며, 부동소수점 배정밀도 난수를 직접 생성하는 dSFMT 변형도 있다. 다만 선형성이라는 근본 성질은 그대로다.

바깥에서는 완전히 다른 설계들이 사실상 새 표준이 되었다.

생성기	상태	특징	약점
PCG64	128비트	LCG + 비선형 출력 순열, 통계 성능 우수	암호학적 안전성 없음
xoshiro256++	256비트	매우 빠름, 점프 함수 제공	선형 기반, 시드 초기화 주의
Philox4x32	없음(키+카운터)	카운터 기반, 완전한 병렬 재현성	라운드 수만큼 연산 비용

NumPy가 1.17에서 기본 생성기를 PCG64로 바꾼 것이 이 흐름을 상징한다. MT가 “틀렸다”기보다, 더 작은 상태로 더 빠르고 더 깨끗한 통계 성질을 내는 선택지가 생겼다는 쪽이 정확하다.

6. 병렬 몬테카를로에서의 스트림 분리[편집]

MT의 진짜 아픈 곳은 병렬 컴퓨팅 환경이다. 스레드마다 독립적인 난수 스트림이 필요한데, 방법마다 위험도가 다르다.

서로 다른 시드를 준다 — 가장 흔하고 가장 위험한 방법. 시드 공간이 시드 함수의 입력 크기(흔히 32비트)로 제한되면 서로 다른 시드가 겹치는 부분 수열을 만들 확률을 통제할 수 없고, 초기 상태끼리 상관을 가질 수도 있다. seed = thread_id 는 특히 나쁘다.
점프 어헤드(jump-ahead) — 상태를 $2^k$ 스텝 앞으로 한 번에 밀어 스레드마다 겹치지 않는 구간을 배정한다. MT에도 다항식 기반 점프 함수가 있지만 상태가 커서 점프 다항식 계산 자체가 무겁다.
동적 생성기 생성(dynamic creator) — 스레드마다 아예 다른 특성다항식을 갖는 MT 파라미터 집합을 만들어 준다. MT 진영의 정공법이지만 준비 과정이 번거롭다.
카운터 기반 생성기 — Philox처럼 상태 대신 (키, 카운터)에서 값을 직접 계산하면, 스레드·시각·입자 인덱스를 카운터에 그대로 넣어 스트림을 나눌 수 있다. 스케줄링 순서와 무관하게 결과가 재현되므로 GPU 컴퓨팅 환경의 사실상 표준이 되었다.

같은 시드로 두 번 돌렸는데 GPU 결과가 미묘하게 다르다면, 커널 실행 순서에 의존하는 스트림 배정을 쓰고 있을 가능성이 높다.² 준-몬테카를로 계열(소볼 수열)처럼 애초에 결정론적 점열을 쓰는 접근과의 차이도 여기서 갈린다.

7. 그래서 지금 뭘 써야 하나[편집]

기존 코드의 결과를 재현해야 한다 → MT19937 그대로. 재현성이 최우선이면 생성기를 바꾸지 않는 것이 맞다.
새 단일 스레드 시뮬레이션 → PCG64나 xoshiro256++.
대규모 병렬·GPU → Philox 같은 카운터 기반 생성기.
보안·암호 용도 → 셋 다 아니다. OS가 제공하는 암호학적 생성기를 쓴다.

어느 쪽을 쓰든 결과를 신뢰하려면 시드와 생성기 종류를 로그에 남기는 것이 기본이다. 검증 및 확인의 관점에서 난수 스트림은 입력 데이터의 일부이지 환경 변수가 아니다.³

8. 관련 문서[편집]

“우리는 시뮬레이션 코드인데 무슨 상관이냐” 싶겠지만, 그 시뮬레이션 코드가 나중에 온라인 추첨이나 A/B 테스트 배정에 재활용되는 전개는 생각보다 흔하다. ↩
부동소수점 합산 순서 문제(부동소수점 연산)와 증상이 비슷해서 원인 진단이 헷갈리기 쉽다. 난수 소비 횟수를 세어 보면 대개 금방 갈린다. ↩
논문 재현성 체크리스트에 “시드 명시”가 들어간 지는 꽤 됐지만, 생성기 이름까지 적는 곳은 아직도 소수다. 파이썬 버전이 바뀌면서 기본 생성기가 달라지면 시드만으로는 재현이 안 된다. ↩