의사 난수

Pseudorandomness

의사 난수열은 완전히 결정적이고 반복 가능한 [1]프로세스에 의해 생성되었음에도 불구하고 통계적으로 랜덤으로 보이는 수열입니다.

배경

랜덤 번호의 생성은 랜덤 샘플링, 몬테카를로 방법, 보드 게임 또는 도박과 같은 다양한 용도로 사용됩니다.그러나 물리학에서는 중력가속과 같은 대부분의 과정이 결정론적이며, 이는 그들이 항상 같은 출발점에서 같은 결과를 만들어 낸다는 것을 의미합니다.일부 주목할 만한 예외는 방사성 붕괴와 양자 측정으로, 둘 다 기초 물리학에서 정말로 랜덤한 과정으로 모델링됩니다.이러한 과정은 난수의 실용적인 소스가 아니기 때문에, 사람들은 [2]결정론적 프로세스에 의해 생성되었음에도 불구하고 정말로 랜덤한 시퀀스의 예측 불가능성을 가진 의사 난수를 사용합니다.

많은 응용 프로그램에서 결정론적 과정은 의사난수 발생기라고 불리는 컴퓨터 알고리즘이며, 우선 랜덤 시드라고 불리는 숫자를 제공해야 한다.같은 시드가 매번 같은 시퀀스를 생성하기 때문에 특히 패턴의 예측 불가능성이 중요한 [3]보안 어플리케이션에서는 시드를 잘 선택하고 숨겨두는 것이 중요합니다.

시퀀스를 예측할 수 없는 것이 중요한 경우에 사람들은 방사성 붕괴, 방송국 간에 튜닝된 라디오에서 수집된 대기 전자파 소음 또는 사람들의 키 [1][4]입력의 혼합 타이밍과 같은 무작위 숫자의 물리적 선원을 사용했다.이러한 수치를 얻기 위해 필요한 시간 투자는 타협으로 이어집니다. 즉, 이러한 물리 판독치 중 일부를 의사 난수 발생기의 시드로 사용합니다.

역사

현대 컴퓨팅 이전에 난수를 필요로 하는 연구자는 다양한 수단(다이스, 카드, 룰렛 [5]휠 등)을 통해 난수를 생성하거나 기존의 난수 표를 사용합니다.

연구원들에게 임의의 숫자의 즉각적인 공급을 제공하려는 첫 번째 시도는 1927년, 캠브리지 대학 출판부가 L.H.C.에 의해 개발된 41,600자리 숫자의 표를 출판했을 때였다. 티펫.1947년, RAND Corporation은 룰렛 [5]휠의 전자 시뮬레이션을 통해 숫자를 생성했습니다. 그 결과는 결국 1955년에 100,000개의 정상 편차를 가진 A Million Random Digits로 출판되었습니다.

계산의 복잡성

이론적인 컴퓨터 과학에서, 만약 그 클래스의 어떤 상대도 그것을 유의한 [6]이점을 가진 균일한 분포와 구별할 수 없다면, 분포는 적대자의 클래스에 대해 의사 난수이다.이 의사난수 개념은 계산 복잡도 이론에서 연구되며 암호학에 응용된다.

공식적으로는, S와 T를 유한 집합으로 하고, F → {f: S → T}를 함수의 한 종류로 하자.F의 각 분포와 F 의 통계적 거리(X가D에서 되고 F가Y에서 샘플링되는 경우 S 위의 분포 D는 F에 대한 의사 난수입니다., 최대 ε 。

전형적인 어플리케이션에서 클래스 F는 한정된 자원을 가진 계산 모델을 기술하며, 클래스 F는 F에 대해 의사난수인 특정 속성을 가진 분포 D를 설계하는 데 관심이 있다.분포 D는 의사난수 [7]발생기의 출력으로 지정되는 경우가 많습니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ a b George Johnson (June 12, 2001). "Connoisseurs of Chaos Offer A Valuable Product: Randomness". The New York Times.
  2. ^ S. P. Vadhan (2012). Pseudorandomness. pseudorandomness, the theory of efficiently generating objects that “look random” despite being constructed using little or no randomness
  3. ^ Mark Ward (August 9, 2015). "Web's random numbers are too weak, researchers warn". BBC.
  4. ^ Jonathan Knudson (January 1998). "Javatalk: Horseshoes, hand grenades and random numbers". Sun Server. pp. 16–17.
  5. ^ a b "A Million Random Digits". RAND Corporation. Retrieved March 30, 2017.
  6. ^ Oded Goldreich.계산의 복잡성: 개념적 관점.케임브리지 대학 출판부2008.
  7. ^ "Pseudorandomness" (PDF).

추가 정보

외부 링크