난수 생성기

랜덤 넘버 제너레이터는 무엇인가?

랜덤 넘버 제너레이터 (RNG)는 패턴이 보이지 않는 숫자를 생성하는 도구 또는 알고리즘이다. — 각 출력은 이전 출력과 독립적이며, 범위 내의 모든 값이 동일한 확률로 나타날 가능성이 있다. 랜덤 넘버는 통계학, 게임, 암호학, 과학적 시뮬레이션 및 컴퓨터 프로그래밍에 필수적이다.

진정한 무작위성은 물리적 현상에서 오는 것이며, 이는 불확실성이 내재되어 있다: 방사성 붕괴, 대기 중 잡음, 전자 회로 내 열 잡음 또는 양자 터널링 이벤트. 하드웨어 RNG는 이러한 현상을 측정하여 진정한 무작위 비트 스트림을 생성한다. 서비스인 random.org는 라디오 수신기를 통해 대기 중 잡음을 수집하여 진정한 무작위 숫자를 제공한다.

컴퓨터에서 생성된 무작위 숫자는 기술적으로 프세우드 랜덤이다 — 이는 결정론적인 시퀀스가 랜덤처럼 보이지만 초기값인 시드에 의해 완전히 결정된다. 동일한 시드를 사용하면 프세우드 랜덤 넘버 제너레이터 (PRNG)는 동일한 시퀀스를 생성한다. 이는 실제로 과학적 시뮬레이션에서 재현 가능성을 위해 유용하다: 시드를 설정하고, 기록하고, 나중에 결과를 재현할 수 있다.

프세우드 랜덤 넘버 제너레이터는 어떻게 작동하는가?

현대 PRNG는 우수한 통계적 특성을 가진 수학적 알고리즘을 사용하여 시퀀스를 생성한다. 가장 널리 사용되는 알고리즘은 Mersenne Twister (MT19937)로, 1997년 Matsumoto와 Nishimura에 의해 개발되었다. 이는 2^19937 − 1 (약 6,000 자리 수)까지 반복하기 전에 모든 표준 통계 테스트를 통과하고, Python, PHP, Ruby, R 및 많은 다른 언어의 기본 RNG이다.

새로운 알고리즘에는 xoshiro/xoroshiro (매우 빠르며, 작은 상태)와 PCG (Permuted Congruential Generator) (우수한 통계적 품질과 작은 상태)가 포함된다. 암호학적 응용 프로그램에선 표준 PRNG는 부적합하다 — 표준 PRNG는 공격자가 충분한 출력을 알면 예측할 수 있기 때문이다.

웹 브라우저는 crypto.getRandomValues() API를 통해 CSPRNG에 접근할 수 있으며, 이 계산기는 이 API를 사용하여 무작위 숫자를 생성한다. 이는 Math.random()보다 훨씬 더 안전하다 — 이는 단순한 PRNG를 사용하고, 보안에 민감한 응용 프로그램에 사용해서는 안된다.

랜덤 넘버의 일반적인 용도

게임 및 엔터테인먼트: 주사위 굴리기, 카드 섞기, 절차적 레벨 생성, 보상 시스템, NPC 행동 무작위화. 로그라이크 게임 (Nethack, Spelunky, Hades)의 전체 경험은 높은 품질의 무작위성과 공정한데다 예측할 수 없는 무작위성에 의존한다.

로또 및 라플스: 상금의 무작위 선택, 경품, 심판단, 드래프트 픽, 경쟁자들 사이에 제한된 자원 할당에 대한 공정한 할당을 위해 무작위 선택. 진정한 무작위 선택은 편향이 없다.

과학적 시뮬레이션 (몬테 카를로 방법): 무작위 숫자가 몬테 카를로 시뮬레이션을 구동하며, 반복적인 무작위 샘플링을 사용하여 복잡한 수학적 결과를 근사한다. 응용 프로그램에는 π 추정, 금융 파생상품 가격 추정, 핵 반응 모델링, 기후 예측 및 약물 상호작용 연구가 포함된다.

통계학 및 연구: 샘플링을 위한 무작위 숫자, 임의 할당 (임의 할당된 임의 할당), 신뢰 구간을 위한 부트스트랩 샘플 생성, 머신 러닝의 교차 검증 모두 무작위 숫자가 필요하다.

암호학 및 보안: 암호화에 사용되는 키 생성, 세션 토큰 생성, CAPTCHA 챌린지, 일회용 패스워드 (OTP/2FA), 패스워드 해싱에 사용되는 솔트 값, 암호학적 프로토콜의 nonce 모두 고품질의 무작위성을 필요로 한다. 암호학적 응용 프로그램에서 약한 무작위성은 치명적일 수 있다 — 이는 실제 세계 보안 침해로 이어졌다.

컴퓨터 프로그래밍: 테스트 데이터 생성, 로드 테스트, 퍼징 (소프트웨어에 무작위 입력을 제공하여 버그를 찾는 것), A/B 테스트 할당, 셔플 알고리즘 (스포티파이의 "셔플" 기능과 같은 것), 시뮬레이션 테스트.

공정성과 통계적 기대치

공정한 난수 생성기는 범위 내의 각 값에 동일한 확률을 부여합니다. 1-6 범위 (주사위와 같은)에서 각 숫자는 약 1/6 ≈ 16.67%의 시간 동안 많은 롤에서 나타나야 합니다. 그러나 짧은 기간 동안의 편차는 일반적이고 예상되는 것입니다 - 이것이 확률이 실제로 말해주는 것입니다.

대수적 확률의 법칙은 시도 횟수가 증가할수록 관찰 빈도는 이론적 확률로 수렴한다는 것을 말합니다. 12 번 주사위를 굴려 {1,3,5,6,2,1,4,3,2,6,5,4} - 정확히 2 개의 숫자가 아닌 것을 볼 수 있습니다. 60,000 번 주사위를 굴리면 10,000 개의 숫자가 매우 근접합니다. 이 수렴은 법칙에 의해 보장되지만 짧은 기간의 패턴은 아닙니다.

게이머의 오류는 독립적인 무작위 이벤트의 과거 결과가 미래의 결과에 영향을 미치는 잘못된 믿음입니다. 5 개의 머리가 연속해서 나온다 해서 머리가 나올 확률이 떨어진다는 것은 아닙니다. 각 굴림은 독립적이며 주사위는 기억력이 없습니다. 유사하게, 이전에 7이 나온 난수 생성기가 다음 호출에서 7이 나올 확률이 낮아진다.

과학에서 난수 생성: 몬테 카를로 방법

몬테 카를로 방법은 분석적으로 어려운 또는 불가능한 문제를 해결하기 위해 무작위 샘플링을 사용합니다. 명백한 이유로 몬테 카를로 카지노 (몬테 카를로 방법의 이름은)와 같은 이름이 붙여졌습니다. 이러한 방법은 결정론적인 문제를 확률론적인 문제로 변환하여 시뮬레이션으로 해결할 수 있습니다.

π 추정: 단위 사각형 내의 무작위 점을 생성하고 (x,y 각 [0,1] 내의 균일 분포), 단위 원 내의 점의 수를 세어 (x² + y² ≤ 1). 비율은 π/4입니다. 1,000,000 개의 무작위 점을 생성하면 π를 약 3-4 자리까지 추정할 수 있습니다. 이것은 π를 계산하는 효율적인 방법이 아니지만, 무작위성의 힘을 아름답게 보여줍니다.

금융 모델링: 블랙-숄스 옵션 가격 및 Value at Risk 계산은 수천 개의 가능한 미래 가격 경로를 사용하여 무작위 숫자를 시뮬레이션합니다. 각 시뮬레이션 경로는 하나의 가능한 미래를 나타냅니다. 수백만 개의 시뮬레이션의 결과 분포는 포트폴리오 수익률의 확률 분포를 제공합니다.

의약품 개발: 몬테 카를로 시뮬레이션은 약물 분자와 표적 단백질 간의 상호 작용을 모델링하여 후보 약물이 표적 단백질에 결합할 가능성을 예측합니다. 실험실 실험의 수를 줄여 약물 개발 비용을 수십억 달러節約합니다.

유니크한 무작위 숫자 생성 (대체 없이)

때로는 반복되지 않는 무작위 숫자가 필요합니다. 예를 들어 카드 덱을 섞는 경우, 참가자에게 그룹을 할당하는 경우 또는 로또 당첨자를 선택하는 경우입니다. 이것은 대체 없이 샘플링 (대체와 함께 샘플링과 반대되는)이라고합니다.

표준 알고리즘은 이에 대한 Fisher-Yates 섞기 (또는 Knuth 섞기)입니다. n 개의 요소가 있는 배열에 대해: 마지막 요소부터 시작하여 전체 배열 (자신 포함)에서 무작위로 선택된 요소와 교환하고, 두 번째로 마지막 요소로 이동하여 그 요소와 무작위로 선택된 요소와 교환하고, 계속합니다. 결과는 O(n) 시간에 균일한 무작위 순열입니다.

k 개의 유니크한 무작위 숫자를 범위 [min, max]에서 생성하려면: 범위 내의 모든 값의 배열을 생성하고 Fisher-Yates를 적용하고, 첫 k 개의 요소를 취합니다. 이로써 k 개의 값의 각 조합이 모두 가능성이 같습니다. - 대체 없이 truly 균일한 샘플입니다.

일상 생활에서 무작위 숫자

무작위 숫자 생성기는 놀랍게도 실용적인 일상적인 결정을위한 유용합니다:

결과를 결정하기 위해: 두 개의 동등한 옵션 중 하나를 선택할 때, 무작위 숫자는 결정에 대한 과도한 생각을 피할 수 있습니다. 연구에 따르면 사람들은 정말로 동등한 선택을 너무 오래 고민할 때, 그들은 무작위로 선택했을 때보다 결과에 대해 더 행복하지 않게 만드는 편견을 도입합니다.

일정과 계획: 무작위 회전 스케줄은 시간에 걸쳐 공정성을 보장합니다. 환상 드래프트에서 첫 번째를 선택하는 사람, 선호하는 시프트를 받는 사람, 회의에서 첫 번째로 논의되는 주제 — 무작위 할당은 편견과 불공정성의 인식이 제거됩니다.

학습 및 연습: 학생들은 플래시 카드를 사용하여 무작위 순서가 학습에 도움이 됩니다. 카드 15의 답을 알고 있는 것과 같은 "문맥적 단서" (카드 14의 답을 최근에 답변한 것)를 피하기 위해. 무작위로 섞인 연습 문제는 블록 연습보다 장기적 인 보존을 강화하는 증명된 기술 (인터리브드 프랙티스)입니다.

창의적 영감: 작가, 예술가 및 음악가들은 무작위 단어 생성기, 프롬프트 생성기 및 무작위 제약 도구를 사용하여 창의적 블록을 극복합니다. 임의로 부과된 제약은 예상치 못한이자 흥미로운 창의적 해결책을 강제합니다.

난수와 프로세서 생성

비디오 게임은 난수로 구축됩니다. 미니크래프트의 세계 생성에서 랜덤 타일 생성에서 적 AI 행동의 섞음에 이르기까지, 고품질의 난수는 재생할 수 있는, 예측할 수 없는 경험을 만듭니다. 프로세서 콘텐츠 생성 (PCG)은 수학적 제약을 사용하여 랜덤 숫자와 함께 광범위한 콘텐츠를 최소한의 수동 노력으로 생성합니다. - No Man's Sky의 18 quintillion 행성은 모두 랜덤 시드에서 생성되었습니다.

Roguelike 게임인 Nethack, Spelunky 및 Hades는 프로세서 레벨 생성을 통해 장르를 정의합니다. 각 실행은 다른 던전, 적 배치 및 아이템 배포를 생성합니다. 게임은 랜덤한 결과가 플레이어가 즉시 죽게 만드는 것을 방지하기 위해 랜덤 시드를 정의합니다. 많은 Roguelikes는 플레이어가 동일한 실행을 재생하거나 흥미로운 시드를 다른 사람과 공유할 수 있도록 시드를 표시합니다.

테이블 게임은 수세기 동안 물리적 난수 (주사위, 섞인 카드, 스피너)를 사용했습니다. 디지털 동등체는 이러한 분포를 정확하게 모방해야합니다. 표준 d6 주사위 굴리는 {1,2,3,4,5,6} 범위 내에서 균일 분포를 사용합니다. 섞인 덱에서 추출하는 것은 랜덤 순열을 사용합니다. 일부 게임은 주사위 풀 (여러 주사위를 굴려, 가장 높은 것을 취함) 또는 주사위에 이점/장점을 사용 - 의도된 확률 분포를 달성하기 위해 주의 깊은 통계적 설계가 필요합니다.

균일 난수에서 다른 분포를 생성하는 방법

대부분의 RNG는 0과 1 사이에 균일하게 분포하는 숫자를 생성합니다 (또는 정수 범위). 종종 우리는 다른 분포를 따르는 난수를 생성해야합니다 - 정규, 지수, 포아ソン 등. 이러한 분포는 변환 방법을 사용하여 균일 난수에서 생성할 수 있습니다.

Box-Muller 변환은 두 개의 균일 난수 U₁ 및 U₂에서 정규 분포를 생성합니다: Z₁ = √(−2ln(U₁)) × cos(2πU₂) 및 Z₂ = √(−2ln(U₁)) × sin(2πU₂). Z₁ 및 Z₂은 표준 정규 분포 N(0,1)입니다. Z × σ + μ로 스케일링하여 N(μ,σ²)를 얻습니다.

역함수 변환 방법은 누적 분포 함수 (CDF)의 역함수를 사용합니다. 지수 분포에 대한 λ: X = −ln(1−U)/λ에서 U는 [0,1] 범위 내의 균일 난수입니다. 이 방법은 분석적으로 역함수화할 수 있는 CDF가 있는 모든 분포에 작동합니다.

난수성 검증 테스트

난수 생성기가 실제로 난수인지 확인하는 방법은 무엇입니까? 통계적 테스트는 truly random한 시퀀스가 나타내는 패턴을 확인하기 위해 난수 시퀀스의 패턴을 확인합니다. NIST 통계 테스트套는 15개의 테스트를 포함하여 암호화 응용 프로그램을 평가하기 위해 난수 생성기를 평가하는 데 사용됩니다. 주요 테스트에는 다음과 같은 테스트가 포함됩니다.

Frequency Test (Monobit): 0과 1이 등빈도(unequal frequency)로 나타나는지 확인합니다. 60%의 확률로 앞면이 나올 때 coin이 비뚤어지면 이 테스트를 실패합니다.

Runs Test: 연속적인 동일한 비트(Consecutive identical bits)의 수를 확인합니다. 비뚤어진 패턴을 나타내는 너무 긴 연속적인 비트가 나타나면 난수 패턴이 아님을 나타냅니다. truly random한 시퀀스는 run 길이의 예측 가능한 분포를 나타냅니다.

Serial Test: 쌍, 삼중, 사중의 값이 등빈도로 나타나는지 확인합니다. 생성기가 1,2,3,4,5,6,1,2,3,4,5,6...의 시퀀스를 생성하면 빈도 테스트를 통과하지만 시리얼 테스트를 실패합니다. 쌍은 난수 패턴이 아님을 나타냅니다.

TestU01 "BigCrush" 테스트套는 가장 엄격한 실용적인 테스트로 간주됩니다. - 106개의 테스트를 실행하고 더 작은 테스트套를 통과하는 많은 알고리즘을 거부합니다. PCG와 xoshiro와 같은 현대 알고리즘은 BigCrush를 통과하지만, 초기 C 라이브러리에서 사용된 선형 대체 생성기는 여러 테스트를 실패하고 품질이 높은 응용 프로그램에 사용되지 않아야 합니다.

이 난수 생성기를 사용하는 방법

최소 및 최대 값을 설정하여 범위를 정의합니다. "how many"를 설정하여 한 번에 여러 숫자를 생성합니다. "no repeats" 옵션을 활성화하여 유니크한 숫자 목록을 생성합니다 (샘플링 without replacement) - 로또 번호, 카드 뽑기, 또는 반복되지 않는 참가자 할당에 적합합니다. 생성된 시퀀스는 브라우저의 암호화 난수 API를 사용하여 고품질의 결과를 제공합니다. 로또 사용 시, 로또의 범위 내에서 필요한 선택 수만큼 숫자를 생성하고, 로또 사용 시, 순차적으로 할당된 숫자를 뽑습니다. 결과는 클릭할 때마다 새로 생성되며, 이전 결과는 저장되거나 추적되지 않습니다.