컴퓨터가 만든 난수는 얼마나 무작위인가, 의사난수의 원리

컴퓨터가 흔히 만드는 난수는 진짜 무작위가 아니라 정해진 계산 규칙으로 만든 의사난수다. 의사난수 생성기는 씨앗이라고 부르는 처음 값 하나를 받아, 같은 계산을 되풀이하며 무작위처럼 보이는 수를 차례로 내놓는다. 씨앗이 같으면 나오는 수열도 언제나 똑같다. 게임이나 모의실험에는 이것으로 충분하지만, 암호처럼 상대가 다음 수를 맞히면 안 되는 곳에서는 훨씬 엄격한 조건이 필요하다.

명령을 따르는 기계의 한계

컴퓨터 프로그램은 같은 입력을 받으면 같은 결과를 낸다. 이 성질 덕분에 컴퓨터를 믿고 쓸 수 있지만, 바로 그 성질 때문에 컴퓨터는 스스로 예측할 수 없는 값을 만들어 내지 못한다. 그래서 1940년대 초기 컴퓨터 시절부터 사람들은 계산으로 무작위를 흉내 내는 방법을 연구했다. 존 폰 노이만은 "계산으로 난수를 만들려는 사람은 누구나 죄를 짓고 있는 것"이라는 농담을 남겼는데, 진짜 무작위가 아니라는 사실을 잊지 말라는 뜻이었다.

씨앗 하나에서 자라는 수열

오래 쓰인 방법 가운데 하나는 선형 합동 생성기다. 직전의 수에 정해진 수를 곱하고 다른 수를 더한 뒤, 어떤 큰 수로 나눈 나머지를 다음 수로 삼는다. 계산은 단순하지만 곱하고 더하는 수를 잘 고르면 결과는 꽤 고르게 흩어진다. 다만 이 방식은 결국 같은 수가 다시 나오며 수열 전체가 되풀이된다. 되풀이가 시작되기까지의 길이를 주기라고 한다.

1997년에 발표된 메르센 트위스터는 주기가 2의 19937제곱에서 1을 뺀 값이라는 엄청난 길이를 가져, 지금도 여러 프로그래밍 언어가 기본 난수 생성기로 쓴다. 주기가 길고 수가 고르게 퍼진다고 해서 무작위라는 뜻은 아니다. 메르센 트위스터는 출력값을 충분히 모으면 내부 상태를 거꾸로 계산해 낼 수 있어서, 그 뒤에 나올 수를 모두 알아낼 수 있다.

무작위처럼 보이는지 시험하기

어떤 수열이 무작위답게 행동하는지 확인하는 검사는 여러 가지가 있다. 0부터 9까지의 숫자가 비슷한 횟수로 나오는지, 같은 숫자가 연달아 나오는 길이가 우연히 기대할 만한 수준인지, 앞의 수와 뒤의 수 사이에 관계가 보이지 않는지를 살핀다. 좋은 의사난수는 이런 검사를 대부분 통과한다. 그러나 검사를 통과했다는 것은 그 검사로는 규칙을 찾지 못했다는 뜻일 뿐, 규칙이 없다는 증명은 아니다.

쓰임	필요한 성질	알맞은 방식
게임, 모의실험	빠르고 고르게 퍼짐, 다시 재현 가능	일반 의사난수 생성기
암호 키, 인증 번호	앞의 값을 알아도 다음 값을 맞힐 수 없음	암호용 난수 생성기
추첨, 복권	누구도 결과를 미리 정할 수 없음	물리적 무작위 원천과 공개 검증

암호에 필요한 난수

암호 키를 만들 때 쓰는 난수는 앞에서 나온 값을 아무리 많이 알아도 다음 값을 맞힐 확률이 찍는 것과 다르지 않아야 한다. 암호용 난수 생성기는 이를 위해 풀기 어렵다고 알려진 수학 문제나 암호 알고리즘을 계산 규칙으로 쓴다. 그리고 씨앗만큼은 계산이 아닌 곳에서 얻는다. 운영체제는 키보드를 누르는 간격, 마우스의 움직임, 하드디스크와 네트워크의 미세한 시간 차이 같은 예측하기 어려운 값을 모아 씨앗으로 삼는다. 요즘의 많은 처리 장치에는 회로 속 전자의 열잡음처럼 물리적으로 무작위인 현상을 읽어 내는 장치가 들어 있다.

씨앗이 약하면 생성기가 아무리 좋아도 소용이 없다. 실제로 장치를 켜자마자 씨앗을 만들 재료가 부족한 상태에서 암호 키를 만들어, 서로 다른 기기에서 같은 키가 생기는 사고가 보고된 적이 있다. 난수의 품질은 수식만이 아니라 처음 값을 어디서 얻느냐에 달려 있다.

씨앗이 같으면 결과가 같다는 성질은 단점만은 아니다. 과학 연구에서 컴퓨터 모의실험을 할 때 씨앗 값을 함께 적어 두면, 다른 연구자가 똑같은 무작위 수열로 실험을 다시 해 볼 수 있다. 게임에서도 같은 씨앗으로 같은 지도를 만들어 여러 사람이 같은 조건에서 겨루게 한다. 재현할 수 있는 무작위는 의사난수만이 줄 수 있는 장점이다.

남은 질문

진짜 무작위가 무엇인지에 대한 답은 수학과 물리학의 경계에 걸려 있다. 수학에서는 그 수열을 만들어 내는 가장 짧은 프로그램이 수열 자체만큼 길면 무작위라고 정의하는 방법이 있지만, 주어진 수열이 이 조건을 만족하는지 일반적으로 판정하는 방법은 없다는 것이 증명되어 있다. 물리학에서는 양자역학의 측정 결과가 원리적으로 예측할 수 없는 무작위의 원천으로 여겨지며, 이를 이용한 난수 생성 장치가 만들어지고 있다. 우리가 쓰는 무작위가 얼마나 무작위인지 끝까지 확인하는 방법은 아직 없다.