의사 난수 생성기 편집하기

의사난수 생성기(pseudorandom number generator, 擬似亂數生成器)는 실제로는 완전히 무작위가 아니지만 통계적으로 무작위성과 유사한 수열을 생성하는 알고리즘이다.

== 개요 ==
의사난수 생성기는 컴퓨터 과학, 암호학, 통계학 등 다양한 분야에서 사용된다. 실제 난수(random number) 생성은 물리적 무작위성을 필요로 하지만, 의사난수는 수학적 알고리즘에 기반해 일정한 시작값(seed)으로부터 결정론적으로 수열을 생성한다. 이러한 특성으로 인해 동일한 시드로부터는 항상 동일한 수열이 재현 가능하다.

== 작동 원리 ==
의사난수 생성기는 일반적으로 초기 시드값을 입력받아 다음 수를 생성하는 반복 알고리즘을 사용한다. 대표적인 방식은 다음과 같다.

* 선형 합동 생성기(Linear Congruential Generator, LCG)
* 메르센 트위스터(Mersenne Twister)
* Xorshift
* PCG(Permuted Congruential Generator)
* 중간제곱법(Mid-square method, 고전적 방식)

이들 알고리즘은 효율성, 수열의 주기, 통계적 품질, 보안성 등 다양한 기준으로 평가된다.

== 보안성과 의사난수 ==
일반적인 의사난수 생성기는 암호학적 용도에는 적합하지 않다. 암호학적 안전성이 요구되는 경우에는 다음과 같은 암호학적으로 안전한 의사난수 생성기(CSPRNG, Cryptographically Secure Pseudorandom Number Generator)가 필요하다.

* Fortuna
* Yarrow
* ChaCha20 기반 PRNG
* 시스템에서 제공하는 /dev/urandom 또는 Windows의 CryptGenRandom 등

이들은 예측 불가능성과 외부 공격에 대한 저항성을 갖추도록 설계되었다.

== 활용 분야 ==
의사난수 생성기는 다음과 같은 분야에서 광범위하게 사용된다.

* 몬테카를로 시뮬레이션
* 게임 개발의 이벤트 처리
* 통계적 샘플링
* 알고리즘 테스트와 디버깅
* 머신러닝의 데이터 셔플링 및 초기화

== 한계와 주기 ==
모든 의사난수 생성기는 유한한 상태 공간을 갖기 때문에 결국 수열이 반복된다. 이 반복되는 길이를 주기(period)라 하며, 주기가 길수록 더 좋은 품질의 난수열로 간주된다. 따라서 고품질의 의사난수 생성기는 가능한 긴 주기와 균등한 분포 특성을 가져야 한다.

== 같이 보기 ==
* [[난수]]
* [[암호학]]
* [[몬테카를로 방법]]
* [[선형 합동 생성기]]
* [[메르센 트위스터]]

== 참고 문헌 ==
* Donald E. Knuth, *The Art of Computer Programming, Volume 2: Seminumerical Algorithms*, Addison-Wesley, 1997.
* Pierre L’Ecuyer, "Random Number Generation", *Handbook of Computational Statistics*, Springer, 2012.
* M. Matsumoto and T. Nishimura, "Mersenne Twister: A 623-dimensionally equidistributed uniform pseudorandom number generator", *ACM Transactions on Modeling and Computer Simulation*, 1998.

== 각주 ==