1. 개요
시스템적으로 임의의 수를 만들어 적용하는 기준을 말한다.2. 상세
역설적이게도, 컴퓨터는 싱글코어 기준으로는 난수를 만들 수 없다. 1대의 CPU로는 무의식적인 선택, 또는 우연에 의하는 선택을 할 수 없기에 기본적으로 정해진 입력에 따라 정해진 값을 낼 뿐이다. 전문용어로는 '결정적 유한 오토마타(Deterministic Finite Automata)'. 흔히 보는 랜덤은 정말로 임의의 값이 아니고 특정한 방법으로 계산하거나 몇 밀리초(ms) 단위로 시시각각 변하는 값을 초기값으로 잡고[1] 여러 계산 과정을 거쳐 사람이 볼 때에 마치 임의의 값인 것처럼 보이게 하는 것이다. '의사난수(擬似亂數/Pseudo Random)'라고 한다.흔히 난수표를 쓰는데 난수표가 정해진 이상 결국은 같은 순서로 같은 숫자가 나온다. 패미컴 버전 봄버맨을 시작할 때 1탄의 벽돌들이 대체로 일정하게 배열되는 점을 떠올리면 어느 정도 이해가 갈 것이다. 비슷한 예로 MS-DOS 버전 테트리스에서 나오는 블럭의 순서가 모두 똑같으며, 크레이지 아케이드 테트리스도 난수가 제대로 생성되지 않았던 탓에 테트리스 계의 똥겜으로 전락할 뻔했다. 난수표를 여러 개 만들어 놓고 매번 다른 난수표를 읽히면 이 문제를 해결할 수 있다. 이 난수표를 선택하는 것을 '시드'라고 한다. 그런데 시드값이 똑같으면 선택되는 난수표도 똑같기 때문에 시드값도 난수여야 한다. 즉, 난수를 만들려면 난수가 필요한 문제가 발생하는 것.해결책은 난수를 만드는 것이 아니라 입력으로 받는 것이다. 시드 입력으로 난수표 고르기는 사용자가 그 많은 난수를 일일이 입력하지 않아도 되는 편의를 제공한다. 쉽게 사용할 수 있는 것은 현재 시각으로, 컴퓨터는 밀리초 단위까지 사용하므로 일부러 똑같은 시드를 만드는 건 불가능에 가깝다. 하지만 엄밀히 따지면 현재 시각은
여러 개선책이 있지만 근본적으로 시드를 기반으로 한 랜덤함수는 완전한 무작위라고 보기가 힘들다. 특정 패턴의 경우 영원히 안 나올 수도 있고, 시드값 생성에 요구하는게 너무 적다면 정밀도가 낮을 경우는 전원 패턴이나 타임테이블 논란[3] 같은 극단적인 일도 생길수 있다. 암호화에도 문제가 되는데, 시드 기반 난수로 암호화 키를 생성하는 경우 키 값의 일부를 알고 있다면 나머지 키 값도 유추하는게 가능해질 수 있다. 일반적인 게임에서는 어느정도의 무작위성으로도 충분하지만, 현찰이 오가는 도박 사이트처럼 정말 랜덤이 필요한 경우 시드 기반의 의사랜덤은 쓰지 않는다.
하지만 여러대의 CPU를 사용하는 멀티코어 컴퓨터라면 진짜 난수도 생성 가능하다. 의사난수와 달리 각 CPU의 작동속도를 기준으로 작동하며, 각 CPU가 언제 메모리에 접근해 읽고 쓰는지를 미리 예측하는것은 불가능하기 때문이다.
1997년 개발된 MT19937(후술할 메르센 트위스터의 일종이다.)를 예로 들자면, 이 알고리즘으로 생성된 난수는 623개까지 연속된 난수를 뽑아볼 때 각 난수의 처음 32비트는 동일분포가 보장된다(32-bit accuracy). 다만 623에서 단 하나 늘어난 624개의 연속된 난수만 어떻게 확보한다면 시드값을 털어버릴 수 있는 치명적인 문제가 있어서 보안이 필요한 곳에서 쓰려면 좀 꼼수가 필요하다.[4] 결과값을 공개하기 전에 해시 함수로 원본을 알아내지 못하게 한다든가 난수를 한 번에 생성한 후 순서를 뒤섞어서 공개한다든가. 이런 좋은 MT19937이란 알고리즘은 Python, PHP 등 대부분의 프로그래밍 언어에서도 이미 기본으로 쓰고 있는 알고리즘이고, C/C++에서 쓰고 있는 rand() 함수가 언어 역사만큼 오래된 안 좋은 랜덤 알고리즘을 쓰고 있을 뿐이다.
현실을 재현하는 것이 아닌 실용 프로그래밍, 특히 단방향 암호화를 포함한 보안 계열을 제외한 실제 응용 프로그램 설계에선 완전 난수보다 의사 난수가 더 많은 분야에 유용하다. 의사난수의 '같은 시드는 같은 결과를 부른다'를 장점으로 활용해, 네트워크 게임의 플레이어 간 동기화에서부터 리플레이 모드 구현까지[5] 오만 곳에 써먹을 수 있다. 마찬가지로 도박에서 원하는 결과가 나오게 악용할 수 있다. 이런 걸 난수조절이라고 한다.
3. 난수 발생 방식
난수를 발생시키는 수식엔 여러가지가 있는데, 중앙 제곱법과 합동식 방법 등이 있다. 난수 발생 원리에 대해 자세히 알고싶으면 위키피디아를 참고.3.1. 중앙제곱법
영어 : Mid Square Method일본어 : 中二乗法
의 가운데 a자리
X는 난수 수열, a는 원하는 자릿수(10진법으로), 시드(X0)는 임의의 a자리인 수[6].
Middle-square method. 폰 노이만이 1949년에 고안한 의사난수법. 생성된 품질이 좋지 않기 때문에 그 당시의 컴퓨터면 몰라도 그 이후 시대에는 웬만하면 아래의 선형합동법을 사용한다.[7]
초기 값이 2345이고, 가운데에서 4자리를 선택하여 5개의 난수를 만드는 경우에는 다음과 같다.
#!syntax cpp
#include <stdio.h>
#include <math.h>
int main(void)
{
int i;
long num1 = 1000000, num2 = 100, temp;
double k = 2345, temp1, temp2;
for(i=1; i<=5; i++)
{
temp1 = pow(k, 2);
temp = temp1 / num1;
temp2 = temp1 - temp * num1;
temp = temp2 / num2;
printf("%5d\n", temp);
k = temp;
}
return 0;
}
3.2. 선형합동법
線形合同法 / Linear congruential sequence#!syntax cpp
static UINT32 next = 1;
int __cdecl rand(void)
{
next = next * 1103515245 + 12345;
return (UINT32)(next>>16) & RAND_MAX;
}
void __cdecl srand(unsigned int seed)
{
next = seed;
}
출처
X는 난수 수열. ANSI C 표준은 m = 231, a = 1103515245, c = 12345. 시드는 이 수열에서 X0의 값을 말한다.
__cdecl 은 함수 호출 규약인데, 생략해도 상관없다. 함수에 진입할 때, 나올 때 어떻게 매개변수를 전달하고 처리하는지를 지정하는 컴파일러 키워드이다.
Linear Congruential. 가장 널리 쓰이는 유사난수법.
계산이 매우 빠르기 때문에 초창기부터 컴퓨터에 널리 사용되었으며, 흔히 쓰이는 rand() 함수는 바로 이것이다. 난수분포가 치우쳐 있고, 주기성이 있다는 결점이 있지만 계산속도가 빠르기 때문에 지금도 난수의 품질을 크게 신경쓰지 않는 경우에는 널리 사용된다. 그런데 시드가 같으면 의미도 없기에 보통은 srand(time(0))으로 난수를 초기화한다. 요즘에는 이 과정을 객체 차원에서 수행하는 모듈도 많이 나와 있다.
서울대학교 이인석 교수가 쓴 선형대수 명저 선형대수와 군의 표지가 선형합동법으로 생성된 난수로 빼곡히 채워져있다. [math(a = 1664525, b = 1013904223, x_1=1015568748, m = 2^{32})]이다. 참고로, 표지의 값으로 [math(a, b, x_1, m)]을 구하는 문제가 연습문제로 나와있다.
3.3. 메르센 트위스터
Mersenne-twister. 흔히 mt_rand()라는 이름을 가진다. 메르센 소수라는 것을 이용하며 선형 합동법보다 우수한 난수의 품질과 속도를 인정받아 C++11 부터는 mt19937 이 표준으로 채택되면서 C++11 부터는 아래와 같은 코드로 메르센 트위스터를 이용한 난수생성이 가능하다.#!syntax cpp
#include <iostream>
#include <random>
int main(void)
{
std::random_device random; //하드웨어 리소스를 기반으로 난수를 생성
std::mt19937 engine(random()); //메르센 트위스터 방식으로 난수를 생성하겠다는 선언
std::uniform_int_distribution<int> distribution(0, 100); //난수의 범위와 자료형 정의. rand() % 100과는 다르게 100도 나올 수 있음
auto generated = distribution(engine);
std::cout << generated << std::endl;
}
메르센 트위스터의 작동 원리/수식은 본 문서 타 문단의 알고리즘들과 비교해 훨씬 어렵고 더 복잡하다. 위키백과 참고. 참고로 PHP는 7.1 버전 이전에는 구현이 잘못되어[8] 엉뚱한 난수값을 뱉어냈었다(...).
3.4. XOR 시프트
#!syntax cpp
uint32_t x, y, z, w;
uint32_t xorshift128(void) {
uint32_t t = x;
t ^= t << 11;
t ^= t >> 8;
x = y; y = z; z = w;
w ^= w >> 19;
w ^= t;
return w;
}
Xorshift. XOR과 비트시프트 연산을 사용하는 난수 발생법. 구조상 현대의 컴퓨터에서 연산 속도가 매우 빠르고 품질도 선형합동법보다 좋다. 그렇지만 몇몇 난수 품질 테스트를 통과하지 못하는 경우가 있어 여러 변종이 나와 있다. 아래는 이를 다소 해결한 변종 중 하나인 Xorshift+로 2128 - 1의 주기를 가진다.
#!syntax cpp
#include <stdint.h>
/* The state must be seeded so that it is not everywhere zero. */
uint64_t s[2];
uint64_t xorshift128plus(void) {
uint64_t x = s[0];
uint64_t const y = s[1];
s[0] = y;
x ^= x << 23; // a
s[1] = x ^ y ^ (x >> 17) ^ (y >> 26); // b, c
return s[1] + y;
}
3.5. 몬테 카를로 방법
- 몬테 카를로 방법 문서 참조
4. 진짜 난수 측정
앞선 방법은 좋은 아이디어로 그럴 듯한 난수를 만들어내지만 이들이 만들어내는 난수는 결국 어디까지나 의사난수(Pseudo Random)이다. 시드에서도 설명했지만, 진짜 난수는 입력으로 받아야 한다. 인간이 난수를 입력하는 대신, 자연의 무작위성을 측정해서 난수로 변환하면 된다. 해당 자연계를 완전히 흉내내는 것은 불가능에 가깝기에 의사난수와는 달리 패턴을 특정할 수 없다는 강점이 있다. 특히 양자난수의 경우 불확정성 원리에 의해 시뮬레이션이 원천 봉쇄된다.가장 많이 알려진 것은 True Random Number Generator 사이트로, 이 사이트에서 사용하는 하드웨어는 주변 노이즈를 기반으로 난수를 생성한다. (TRNG) 호주국립대학교(ANU)에서는 양자난수 생성기(QRNG)를 사용하고 있는데, 해당 사이트에서는 진공에서의 양자요동을 측정하여 난수를 생성한다. (ANU QRNG) ANU의 QRNG와 비슷한 것이 바로 가이거 계수기인데, 가이거 계수기를 때리는 방사선 등을 통해 진짜 난수를 쉽게 생성할 수 있다.
Cloudflare는 라바 램프가 나열된 벽을 찍은 화상에서 노이즈를 추출하여 난수를 생성한다.
보안 기능을 제공해주는 하드웨어인 TPM에는 난수생성이 존재한다. 2021년 10월에 출시된 Windows 11의 필수 요구 사항에 TPM이 포함되어서 TPM 모듈을 사서 장착하거나 펌웨어에서 가상 TPM 기능을 켜는 경우가 많아졌다.
삼성전자의 스마트폰 갤럭시 퀀텀 시리즈에는 SK텔레콤에서 개발한 '양자난수생성칩'을 탑재하여 진짜 난수를 생성하여 보안을 강화시켰다.
4.1. 멀티코어 프로세서
멀티코어 프로세서에서 발생하는 데이터 경합을 활용한 난수 생성기이다. 데이터 경합은 여러 스레드가 하나의 데이터에 접근해 읽고 쓸 때 발생하는 현상으로, 가령 데이터에 1을 더한 값을 저장한다 했을 때 그 과정은 데이터를 읽고, 1을 더하고, 저장하는 것으로 나눠져 있기 때문에 데이터를 읽은 뒤 1을 더하는 과정에서 각 스레드에서 만든 임시 변수에 1을 더하면 서로 다른 변수에 1을 더한 값을 저장하기 때문에 여러 스레드에서 1을 더했음에도 값은 1만 오르는 것이다. CPU 작동속도에 따라 이 현상으로 인해 1이 오를 수도 있고 이 현상이 발생하지 않아 2가 오를 수도 있어 난수가 되는 것.여러 CPU의 작동속도 차이에 의해 난수가 발생하기 때문에 싱글코어 환경에서는 작동하지 않는다. 싱글코어에선 CPU 하나에 여러 스레드를 컨텍스트 스위칭으로 돌려가며 작동시키기 때문에 메모리 접근 순서가 일정해지기 때문.
#!syntax cpp
#include <process.h>
#include <stdio.h>
#include <conio.h>
volatile int number;
void Act(void*) {
for (int i = 0; i < 10000000; ++i) {
++number;
}
}
int main(int, char**, char**) {
number = 0;
_beginthread(Act, 0, NULL);
for (int i = 0; i < 10000000; ++i) {
++number;
}
printf("%d", number);
_getch();
return number;
}
위 코드는 7000000~13000000 정도 범위의 값을 무작위로 출력한다.
멀티코어를 활용할 경우 코어 하나를 난수 생성에 할애해야 하기 때문에 시드를 받는 용도로 쓰거나 미리 값을 많이 받아놓고 쓰는 것이 좋다.
5. 관련 문서
[1] 정말 극단적인 예를 들면, 0.001초에 누르면 난수는 1, 0.002초에 누르면 난수는 2.... 이런식으로 시간을 난수에 대입시킨것이다. 물론 실제 계산은 더 복잡하다.[2] 키보드의 키를 누른 시간 간격을 샘플링 한 것, 사용자의 입력 자체, VeraCrypt에서도 쓰인 마우스 움직임 등.[3] 정밀도가 낮은 시드값을 써서 문제되었는데, 당시 증상 때문에 시간만 쓴 것으로 추정되었다.[4] 의사난수인 이상 시드값을 알면 모든 결과를 미리 계산할 수 있다.[5] 스타크래프트의 리플레이 모드를 생각해 보면 된다. 게임의 시드만 저장하면 AI의 모든 판단을 다 저장할 필요가 없어진다.[6] a=6이면 100000 ≤ X0 ≤ 999999 의 범위 중 하나를 쓰라는 말[7] 결정적으로, 의 값이 0일 때 인 의 모든 값이 0이다(...). 회차마다 난수에 상수를 더해봐도 계속 가다 보면 어느 순간 반복되는 일정한 패턴이 나타난다.[8] 더 경악할 만한 사실은 해당 링크에서 나온 소스 코드 부분은 이 그릇된 구현을 바로잡았었는데 PHP 주 제작진에 의해 이전으로 롤백된 상황(...).