1. 난수 생성(Random Number Generation, RNG)의 구분
ㅇ TRNG (True RNG, 순수 난수 생성)
- 동전,주사위 던지기
- 특별하게 설계된 전자적 장치 (백색소음 발생 등)
ㅇ PRNG (Pseudo RNG, 의사 난수 생성)
- 확률 알고리즘 (실제 난수 생성이 아닌 의사 난수 생성 임)
- 여기서, 의사 난수 이란?
. 비록 완전한 랜덤은 아니지만,
. 길이가 아주 길고, 순환(반복)적인 수열을 발생시키며,
. 아주 긴 수열에서 거의 완벽한 랜덤(무작위) 수열에 가까운 통계적 특성을 보임
2. 의사 난수의 생성 방법
ㅇ 선형 합동에 의한 방법 (LCG, Linear Congruential Generator,선형 합동 생성기)
- 정의식 (알고리즘)
. Xn+1 = (a Xn + c) mod m, (n ≥ 0)
- 선택 가능 모수 넷
. X0 : 종자 (Seed) (0 ≤ X0 ≤ m)
. a : 승수 (Multiplier) (0 ≤ a ≤ m)
. c : 증분 (0 ≤ c ≤ m)
. m : 계수 (Modulus) (m ≥ 0)
- 호출 형태
. 가장 처음에는 시드(seed)라는 초기값을 입력으로 하여, 난수 생성 알고리즘을 호출하고,
. 그 이후에는 이전에 만들어낸 수를 입력으로 하여, 일련의 난수 생성 알고리즘을 호출하게 됨
- 생성값 : 통상, [0,1) 사이에 일련의 실수를 생성 함
. 즉, Ui = Xi / m
- 특징
. 그이전 난수 Xn으로부터 그다음 난수 Xn+1을 만들어내도록 함
. 항상 작업 시작 전에, 시드(seed)라는 초기값 X0이 필요함
.. 같은 시드에 대해, 항상 예측가능한, 같은 결과를 만들어 냄
. 반복 구간(한번 나온 수열이 계속 되풀이 됨)이 있게됨
.. 따라서, 선택 가능 모수(a,m,c)를 잘 선택해 두어야 함
. 결국, 최장 반복 구간을 얻고자 함
- 1949년 데릭 헨리 레머(Derrick Henry Lehmer)에 의해 최초 제안
ㅇ LFSR (선형귀환이동레지스터)에 의한 방법
- PRBS를 발생시키는 가장 편리하고 빠른 방법
ㅇ ... (추가작성중) ...
3. 의사 난수의 검정
ㅇ 검정의 대상이 되는 주요 특성
- 분포적 특성
- 독립성 검정
- 패턴
ㅇ 실제 난수와 의사 난수 간에 유의미한 차이를 측정하여 무작위성을 검정하게 됨
4. 의사 난수의 특징
ㅇ 확률적으로, 독립 항등 분포(iid,서로 통계적 독립이고 동일한 확률분포)이어야 함
ㅇ 균등확률분포를 갖음
ㅇ ... (작성중) ...