의사 난수 생성기
의사난수 생성기(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.
