배경지식

• 1. 메르센 소수

1. 개요

Mersenne Twister는 1997년 마츠모토 마코토(松本眞)와 니시무라 타쿠지(西村拓士)가 개발한 의사난수 생성기(Pseudorandom Number Generator, PRNG)이다. 현재 가장 널리 사용되는 범용 난수 생성 알고리즘 중 하나로, Python의 random 모듈, Ruby, PHP, Excel, C++의 std::mt19937 등 다양한 프로그래밍 언어와 라이브러리의 기본 난수 생성기로 채택되어 있다.

핵심 특징은 다음과 같다

1. 압도적인 주기 길이

   Mersenne Twister의 가장 큰 특징은 메르센 소수 $2^{19937}-1$을 주기로 가진다는 점이다. 이는 약 $10^{6000}$에 해당하는 천문학적인 수치로, 실질적으로 무한에 가까운 주기를 제공한다.

2. 고속 연산

   Mersenne Twister는 복잡한 수학 연산 대신 비트 단위 연산(XOR, Shift, AND)만을 사용한다. 이러한 연산들은 현대 CPU에서 한 사이클 내에 수행 가능하므로 매우 빠른 난수 생성 속도를 제공한다.

3. 높은 차원 균등성

   Mersenne Twister는 623차원 공간에서 균등 분포를 만족한다. 이는 생성된 난수 시퀀스를 623개씩 묶어 623차원 공간의 점으로 해석할 때, 이 점들이 해당 공간을 균등하게 덮는다는 의미이다.

2. 수학적 기반

2.1 GF(2) 상의 선형 점화식

Mersenne Twister의 핵심은 갈루아 체 GF(2) 위에서 정의된 선형 점화식이다. 이는 내부 상태를 업데이트하는 수학적 기반을 제공한다.

2.1.1 점화식의 정의

내부 상태 벡터 $x_k$에 대해 다음과 같은 점화식이 성립한다:

$$ x_{k+n} := x_{k+m} \oplus (x_k^u | x_{k+1}^l) A $$

여기서:

• $n = 624$: 상태 벡터의 크기
• $m = 397$: 중간 오프셋
• $x_k^u$: $x_k$의 상위 $w-r = 1$비트
• $x_{k+1}^l$: $x_{k+1}$의 하위 $r = 31$비트
• $|$: 비트 연결 연산자
• $\oplus$: XOR 연산
• $A$: $32 \times 32$ 비트 행렬

2.1.2 행렬 A의 구조