난수 생성기

수치해석 통계 마지막 수정: 2026-08-03 04:26:08

1. 개요[편집]

난수 생성기(random number generator), 정확히는 유사난수 생성기(pseudorandom number generator, PRNG)는 완전히 결정론적인 알고리즘으로 난수처럼 보이는 수열을 만들어내는 장치다. 내부 상태 $s$ 를 갖고, 매 호출마다 상태를 갱신하고( $s \leftarrow T(s)$ ) 상태에서 출력을 뽑아낸다( $u = G(s)$ ). 상태와 갱신 규칙이 결정론적이므로 같은 시드를 주면 같은 수열이 나온다.

이건 결함이 아니라 기능이다. 몬테카를로 방법 결과가 이상해서 디버깅해야 할 때, 진짜 물리적 난수를 썼다면 그 케이스를 두 번 다시 재현할 수 없다. 논문에 “시드 12345로 재현 가능”이라고 쓸 수 있는 것, 리팩터링 전후 결과가 비트 단위로 같은지 확인할 수 있는 것 — 검증 및 확인의 절반은 재현성에서 나온다. 폰 노이만이 “산술적 방법으로 난수를 만들려는 사람은 누구나 죄악의 상태에 있다”고 농담한 것도, 그러면서 본인이 중간제곱법을 만들어 쓴 것도 같은 맥락이다.¹

2. 선형합동생성기와 마르사글리아의 정리[편집]

가장 오래되고 가장 단순한 것이 선형 합동 생성기(LCG)다.

x_{n+1} = (a x_n + c) \bmod m

한 줄이면 구현되고 곱셈 한 번에 난수 하나가 나온다. 주기는 최대 $m$ 이고, $c \neq 0$ 일 때 최대 주기 조건은 헐-도벨 정리로 알려져 있다. 문제는 이 구조가 너무 선형적이라는 것이다.

1968년 마르사글리아는 “Random numbers fall mainly in the planes”라는 짧고 살벌한 논문에서, LCG가 뱉는 연속된 $k$ 개 값을 좌표로 삼아 $k$ 차원 점을 찍으면 그 점들이 반드시 유한한 개수의 평행한 초평면 위에만 놓인다는 것을 증명했다. 초평면 개수의 상한은 대략 $(k!\,m)^{1/k}$ 이며, 차원이 올라갈수록 이 값은 처참하게 작아진다. 즉 LCG로 만든 고차원 점 구름은 균일한 게 아니라 격자 껍데기다.

이걸 실물로 보여준 사고가 IBM의 RANDU다. $a = 65539 = 2^{16}+3$ , $m = 2^{31}$ 이라는 (당시 기준으로) 계산이 빠른 조합이었는데, 세 항 사이에

x_{n+2} - 6x_{n+1} + 9x_{n} \equiv 0 \pmod{2^{31}}

이라는 정수 관계가 성립한다. 결과적으로 3차원 점들이 단 15개의 평면에만 놓인다. 2차원 산점도로는 멀쩡해 보이는데 3차원으로 돌려보면 층층이 갈라진 팬케이크가 나온다. 1960~70년대 RANDU로 돌아간 수많은 몬테카를로 방법 계산이 이 때문에 오염됐고, 그중 얼마가 논문으로 남았는지는 아무도 모른다.²

이 격자 구조를 정량화하는 표준 도구가 스펙트럴 검정(spectral test)이다. $k$ 차원 격자에서 이웃한 초평면 사이 거리의 최댓값을 재는데, 이 값이 클수록 나쁘다. Knuth가 TAOCP 2권에서 “지금까지 알려진 검정 중 좋은 LCG와 나쁜 LCG를 가장 잘 구별한다”고 평가한 검정이며, 지금도 LCG 계열 파라미터를 고를 때 기준이 된다.

RANDU·MINSTD·ANSI C rand·소규모 LCG를 실제로 반복시켜 연속 세 출력 (uₙ, uₙ₊₁, uₙ₊₂) 을 단위 정육면체에 찍고 큐브를 텀블링시킨다. 주기적으로 카메라가 격자 축소로 찾아낸 평면 법선 방향에 정렬되는데, 그 순간 RANDU 의 점들이 등간격 세로선 15 개로 무너진다 — 관계식 계수 (9, −6, 1) 도 하드코딩이 아니라 축소가 찾아낸 결과이고, 이웃 선 간격은 min=max=9.2057e−2 = 1/ν₃ 로 실측된다. 아래 2 차원 산점도에서는 평면이 65,531 장이라 고르게 보이는데 3 차원에서 15 장으로 주저앉는 것이 스펙트럴 검정 표의 S₂ 0.9305 대 S₃ 0.0075 로 같이 읽힌다.

LCG의 두 번째 함정은 하위 비트다. $m = 2^k$ 인 LCG에서 $j$ 번째 하위 비트의 주기는 고작 $2^j$ 다. 최하위 비트는 주기가 2 — 즉 0, 1, 0, 1로 진동하거나 상수다. 그래서 옛날 코드에 흔한 rand() % 6 같은 주사위 구현은 하필 가장 쓰레기 같은 비트만 골라 쓰는 짓이었다. LCG를 쓸 거면 상위 비트를 쓰거나, 애초에 나머지 연산 대신 상위 비트 기반 축소를 써야 한다.³

3. 좋은 난수의 조건과 통계 검정[편집]

“좋은 생성기”의 조건은 대략 이렇다.

긴 주기: 소비할 표본 수의 제곱보다 훨씬 커야 한다. 주기 $2^{32}$ 는 요즘 기준으로 몇 초 만에 다 쓴다.
고차원 균일성: $k$ 차원 등분포성(equidistribution). 앞서 본 초평면 문제의 정면 대응.
비트 독립성: 어떤 비트를 뽑아 써도 통계적으로 멀쩡할 것.
속도와 상태 크기: 캐시에 얹히는 작은 상태가 유리하다.
점프 어헤드: 수열을 $2^{128}$ 개 건너뛴 상태를 $O(\log)$ 시간에 계산할 수 있을 것.

이걸 검증하는 도구가 통계 검정 스위트다. 초기 표준은 마르사글리아의 Diehard(이후 확장판 Dieharder)였고, 현재 사실상의 기준은 르퀴예와 시마르의 TestU01이다. TestU01은 강도별로 SmallCrush(빠른 스크리닝), Crush, BigCrush(가장 가혹) 세트를 제공한다. 여기서 “BigCrush를 통과했다”는 표현이 현대 PRNG 소개문에 반드시 등장하는 문구가 됐다. 암호 쪽에서는 NIST SP 800-22 스위트가 별도로 쓰인다.

검정 결과 해석에는 주의가 필요하다. 검정은 수백 개의 p-값을 뱉는데, 완벽한 생성기라도 그중 일부는 우연히 극단값이 나온다. “몇 개 실패”와 “구조적 실패”를 구별하려면 시드를 바꿔 재실행해봐야 하며, 이건 통계적 다중검정 문제 그 자체다.

4. 현대 생성기 계열[편집]

계열	대표	상태/주기	설계 목표
꼬인 GFSR	메르센 트위스터 MT19937	19937비트, 주기 $2^{19937}-1$	초장주기 + 623차원 등분포
xorshift 계열	xoshiro256++	256비트	속도와 상태 크기의 균형
LCG + 출력 치환	PCG	가변	약한 상태전이 + 강한 출력 함수
카운터 기반	Philox, Threefry	무상태(키+카운터)	병렬·GPU 친화

메르센 트위스터(MT19937, 1997)는 20년 넘게 사실상 표준이었다. 주기 $2^{19937}-1$ 에 32비트 정밀도로 623차원 등분포라는 압도적 스펙 덕분에 Python, MATLAB, R, C++ 표준 라이브러리가 모두 채택했다. 단점도 뚜렷하다. 상태가 2.5 KB로 커서 캐시에 부담이고, $\mathbb{F}_2$ 위 선형 점화식이라 선형복잡도 관련 BigCrush 검정을 통과하지 못한다. 또 0이 많은 상태로 시작하면 회복에 수십만 스텝이 걸리는 초기화 취약성이 있다.

xoshiro/xoroshiro 계열은 XOR·시프트·회전만으로 훨씬 작은 상태에서 좋은 품질을 낸다. PCG(O’Neill, 2014)는 발상이 재밌다 — 상태 전이는 그냥 LCG로 두고(선형이라 예측 가능), 출력 단계에서 상태 의존적 시프트·회전 치환을 걸어 선형 구조를 깨버린다. Philox/Threefry(Random123)는 아예 상태 갱신을 버리고, 블록 암호를 축소한 함수에 (키, 카운터)를 넣어 난수를 만든다. $n$ 번째 난수를 순서와 무관하게 $O(1)$ 에 직접 계산할 수 있어서 GPU 커널마다 스레드 인덱스를 카운터로 꽂으면 끝난다. GPU 컴퓨팅 기반 직접 시뮬레이션 몬테카를로나 대규모 입자 계산에서 이 계열이 사랑받는 이유다.

4.1. CSPRNG와는 다르다[편집]

암호학적 안전 난수 생성기(CSPRNG)는 요구 조건이 다르다. 통계적으로 균일한 것으로는 부족하고, 출력을 아무리 많이 봐도 내부 상태나 다음 출력을 다항시간에 예측할 수 없어야 한다. ChaCha20 기반 /dev/urandom, AES-CTR DRBG 같은 것들이며, 반대로 MT19937은 연속 624개 출력만 관측하면 상태 전체가 복원된다. 시뮬레이션용 생성기를 세션 토큰이나 암호 키 생성에 쓰면 사고가 나고, CSPRNG를 몬테카를로에 쓰면 재현성이 곤란해지고 느리다. 용도를 섞지 마라가 이 문단의 전부다.

5. 시뮬레이션 실무 — 시드, 병렬 스트림, 재현성[편집]

난수 품질보다 실무에서 더 자주 사고를 내는 건 운용이다.

시드 기록: 논문·리포트에 시드와 생성기 이름·버전을 반드시 남긴다. 라이브러리 버전이 올라가며 기본 생성기가 바뀌어 결과가 재현되지 않는 사고는 지금도 흔하다.
시계 기반 시드의 함정: 클러스터에서 100개 프로세스를 동시에 띄우고 각자 time()으로 시드를 잡으면 초 단위 해상도에서 여러 프로세스가 같은 수열을 쓴다. 앙상블 평균이 통째로 오염된다.
병렬 스트림 분리: 정석은 점프 어헤드(jump-ahead / leapfrog)다. 하나의 수열을 겹치지 않는 구간으로 잘라 각 랭크에 배정하면 중복이 수학적으로 배제된다. xoshiro와 MT는 점프 함수를 제공하고, 카운터 기반 생성기는 카운터 공간 분할이 곧 스트림 분리다.
임의 시드의 겹침 위험: “그냥 랭크마다 랜덤 시드”는 생일 문제다. 주기 $P$ , 스트림 $n$ 개, 각 길이 $L$ 이면 겹칠 확률은 대략 $n^2 L / P$ 규모로 커진다. 주기가 $2^{19937}$ 급이면 사실상 무시할 수 있지만, 32비트 상태 생성기에서는 실제로 터진다.
결과가 시드에 민감하면 그건 통계 부족: 시드 몇 개 바꿨다고 결론이 뒤집히면 표본 수가 모자란 것이지 생성기 탓이 아니다. 마르코프 연쇄 몬테카를로에서 여러 체인을 독립 시드로 돌려 겔만-루빈 진단을 보는 것도 같은 정신이다.

균일난수 $U(0,1)$ 은 재료일 뿐이고, 실제 시뮬레이션은 거기서 원하는 분포를 만들어 쓴다. 역변환 표본추출로 CDF를 뒤집거나, 정규분포는 박스-뮐러 변환, 일반 밀도는 기각표본추출을 쓴다. 반대로 일부러 난수를 포기하는 길도 있다 — 소볼 수열 같은 준난수(low-discrepancy sequence)는 균일성을 인위적으로 극대화해 수렴률을 $O(N^{-1/2})$ 에서 $O((\log N)^d/N)$ 근처까지 끌어올리고, 라틴 하이퍼큐브 표본추출은 차원별 층화로 분산을 줄인다. 이들은 “난수처럼 보이는 것”이 목표가 아니므로 통계 검정 스위트를 통과하지 못하며, 그래도 정상이다.

6. 관련 문서[편집]

원문은 “Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin.” (1951) 정작 그가 만든 중간제곱법은 상태가 0으로 빨려 들어가 죽어버리는 치명적 결함이 있었다. 죄를 지으려면 제대로 지어야 한다. ↩
RANDU를 옹호하는 유일한 논리는 “당시 하드웨어에서 $2^{16}+3$ 곱셈이 시프트와 덧셈으로 빠르게 되니까”였다. 성능 최적화가 정확도를 통째로 날려먹은 전형적인 사례이며, 지금도 커널을 손으로 튜닝할 때마다 떠올려야 할 교훈이다. ↩
나머지 연산 자체도 문제다. $2^{32}$ 를 6으로 나누면 딱 떨어지지 않으므로 rand() % 6 은 특정 눈이 아주 미세하게 더 자주 나온다. 표본이 수십억 개인 시뮬레이션에서는 이 편향이 검출된다. 정석은 기각을 곁들인 균일 범위 축소(Lemire의 방법 등)다. ↩