Random Number Generator (난수 발생기)

난수 발생기 (Random Number Generator, RNG)

랜덤으로 보이는 일련의 sequence를 만드는 과정을 의미합니다. 

우리가 컴퓨터 상에서 사용하는 랜덤이라는 수는 사실 컴퓨터가 랜덤 하게 생성한 게 아닌 어떤 일련의 규칙을 통해서 우리가 인식하기에 랜덤이라고 보일 뿐입니다.

 

TRNG (True Random Number) vs PRNG (Pseudo Random Number)

TRNG는 물리적인 요소를 통해서 랜덤 수를 생성합니다. 예를 들어서 방사성 붕괴 (Radioactive decay), 열적 노이즈 (Thermal Noise), 그리고 대기 노이즈와 같이 이러한 요소들은 상당히 불확실성 한 특징을 지니고 있기에 이러한 특징을 이용하여 난수를 생성합니다. 

PRNG는 deterministic 한 알고리즘을 이용하여 난수 시퀀스를 생성합니다. 초기 시드 값을 사용해서 시퀀스를 시작하고 그리고 초기 시드 값을 이용해서 특정 수학적 식을 거쳐서 다음 랜덤값이 나오고 다시 값이 반영되어서 지속적으로 수를 만들게 됩니다. 보이기에는 랜덤처럼 보이지만 실제로는 랜덤이 아닌 특징이 있습니다. PRNG를 통해서 시뮬레이션이나 게임에 많이 사용되며 우리가 소프트웨어에서 사용하는 랜덤함수 또한 PRNG의 한 종류입니다.

 

Goal of RNG

난수 발생기의 목표는 다음과 같습니다. 

1. Fast speed and adaptability
2. Long cycle and ability to reproduce any sequence it generates
3. Uniformity and independence

 

Type of TRNG

1. Random Devices

랜덤적 특징을 가진 현상 또는 기계를 이용하여 난수를 만드는 방법입니다. 그러나 해당 방법은 다시 동일한 Sequence 생산이 거의 불가능에 가깝습니다.

• 코인 던지기
• 가이거 계수기를 이용한 particle count
• 원자시계를 이용한 digit 생성 

 

2. Random Number Tables

테이블에 기록된 digit을 이용합니다. 사전에 기록된 정보를 이용하는 방법이지만 해당 방법은 느리며 유용하지가 않습니다. 또한 테이블이 무한대로 길지가 않기 때문에 sequence길이에도 한계가 있습니다.

 

3. Mid Square Method (J. von Neumann)

숫자의 제곱을 했을 때 얻어지는 결과에서 중간 부분을 채용해서 이용하는 방법입니다. 

예를 들어서 난수 (R) = X / 10000이라고 할 때,
X1 = 6632일 때 X1^2 = 43(9834)24이며 중간 부분인 9834가 X2가 되게 됩니다.
X2 = 9834 -> X2^2 = 96(7075)56이며 중간 부분은 7075이며 X3가 됩니다. 

그러나 어느 순간 양수의 correlation이 발생하며 때때로 생성이 불가능한 경우가 있어서 오래 사용되지는 못하였습니다.

 

4. Fibonacci and Additive Congruential Generators

피보나치수열의 규칙을 이용하는 방법으로서, Xi = X_(i-1) + X_(i-2)의 규칙으로 X를 만듭니다.

그리고 난수 (R)는 Xi / m으로 계산하여 난수를 생산합니다. 

문제점은 X의 크기들이 작은 수일 경우 작은 숫자들이 계속해서 따라오며, 또한 X가 피보나치수열에 의해서 지속적으로 커지기 때문에 작은 결과를 얻을 수가 없는 한계가 있습니다.

 

5. Linear Congruential Generators (LCG)

상당히 많이 이용된 방법이며 방식은 다음과 같습니다.

Xi = (aX_(i-1) + c) mod m으로 계산되며 이때 X_0는 Seed입니다.
Ri (난수)는 Xi / m으로 계산됩니다.

해당 접근 법은 a, c, m 값을 잘 설정해 주는 게 필요하며, 잘 설정해줘야만 긴 Sequence를 보장할 수 있습니다.

하지만 단점이 다양하게 존재합니다.

• Xi = (4X_(i-1) + 2) mod 8일 경우 full period가 보장되지 않으며, 심지어 짝수만 계속 생성됩니다.
• Xi =(X_(i-1) + 1) mod 8일 경우, full period가 보장되지만, X값들이 상당히 랜덤 하지 않은 수가 계속 생성됩니다
  (e.g., X1 = 1, X2 = 2,  X3 = 3, ..... )
• m 값이 작을 경우 (20억 이하) 반복되는 주기가 빠릅니다.

 

6. (Recent RNG) Mersenne Twister

해당 방법은 1997년도에 개발되었으며 마찬가지로 PRNG의 한 종류입니다. 

주기의 길이는 2^19937 - 1 길이의 사이클을 가지게 되어서 상당히 긴 랜덤 시퀀스를 보장할 수 있습니다. 사실 상당히 긴 게 아니라 현존 인류가 가진 최고 사양의 컴퓨터로 돌려도 같은 패턴이 반복하는 것을 볼 수 없을 정도로 긴 시퀀스입니다.

메르센 수 (Mn = 2^n - 1)를 이용하여 알고리즘이 동작합니다. 

Seed를 사용하여 624개만큼의 벡터를 먼저 생성하고 보통 seed는 하드웨어 노이즈 또는 오늘 날짜를 이용합니다.
해당 벡터를 이용하여 624개의 유사 난수를 만들고 해당 벡터에 다시 노이즈를 준 후 (Twist 과정) 다시 2번을 반복하여 생성합니다.

현재도 다양한 소프트웨어 (MATLAB, PHP, Python... ) 등에서 사용되고 있습니다.