랜덤성 검정

Randomness test
무작위 시험과 혼동해서는안 된다.

데이터 평가에서 랜덤성 검정(또는 랜덤성에 대한 검정)은 데이터 집합의 분포를 분석하여 랜덤(패턴 없음)으로 설명할 수 있는지 여부를 확인하는 데 사용되는 검정이다.확률론적 모델링에서, 일부 컴퓨터 시뮬레이션에서와 같이, 데이터가 시뮬레이션 실행에 사용하기에 유효하다는 것을 보여주기 위해, 무작위성에 대한 공식적인 테스트를 통해, 잠재적 입력 데이터의 희망 무작위성을 검증할 수 있다.어떤 경우에는 데이터가 소위 "데이터의 런"과 마찬가지로 명백한 비랜덤 패턴을 드러내기도 한다(예: 무작위 0–9를 예상하지만 "4 3 2 1 0 4 3 2 1..."을 발견하고 4를 거의 넘지 않는다).선택한 데이터 집합이 검정에 실패하면 매개변수를 변경하거나 랜덤성 검정을 통과한 다른 랜덤화 데이터를 사용할 수 있다.

배경

무작위성의 문제는 중요한 철학적, 이론적 질문이다.랜덤성에 대한 검정은 데이터 집합에 인식할 수 있는 패턴이 있는지 여부를 결정하기 위해 사용될 수 있으며, 이는 데이터 집합을 생성한 프로세스가 유의적으로 랜덤하지 않음을 나타낼 수 있다.대부분의 경우, 통계 분석은 실제로 무작위성에 대한 검사와는 달리 데이터의 정규성을 찾는 데 훨씬 더 많은 신경을 썼다.오늘날 사용되고 있는 많은 "랜덤 번호 생성기"는 알고리즘에 의해 정의되며, 실제로 의사 무작위 번호 생성기도 마찬가지다.그들이 만들어내는 순서를 사이비 무작위 시퀀스라고 한다.이러한 생성기는 항상 충분히 랜덤한 시퀀스를 생성하는 것이 아니라 패턴을 포함하는 시퀀스를 생성할 수 있다.예를 들어, 악명 높은 랜두 루틴은 스펙트럼 테스트를 포함하여 많은 무작위 테스트를 극적으로 통과하지 못한다.

Stephen Wolfram은 실제 크기보다[2] 훨씬 작은 유효 키 크기를 가지고 있고 카이-제곱 테스트에서 낮은 성능을 보였지만,[1] 규칙 30의 출력에 대한 무작위성 테스트를 사용하였다.[3]잘못된 생각의 무작위 숫자 생성기를 사용하면 통계적 가정을 위반함으로써 실험의 타당성을 의심하게 할 수 있다.NIST 표준과 같이 일반적으로 사용되는 통계 시험 기법이 있지만, 용게 왕은 NIST 표준이 충분하지 않다는 것을 보여주었다.또한, Yongge Wang은[4] 통계 거리 기반 및 반복 로가리듬 기반 시험 기법을 설계하였다.용게 왕과 토니 니콜은[5] 이 기술을 사용하여 2008년에 고정된 잘 알려진 Debian 버전의 OpenSSL 유사성 생성기와 같이 일반적으로 사용되는 유사성 생성기의 약점을 감지했다.

랜덤성에 대한 특정 검정

실제로 사용되는 (의사-)난수 생성기의 종류는 상당히 적다.무작위 숫자 생성기 목록에서 확인할 수 있으며, 다음을 포함한다.

이러한 서로 다른 발전기는 승인된 시험 세트를 통과하는 데 있어 다양한 성공 정도를 가진다.널리 사용되는 몇 개의 발전기는 시험에서 다소 불량하게 실패하는 반면, 다른 '더 나은' 발전기와 이전 발전기(시험의 모든 현재 배터리를 통과했고 이미 존재했다는 의미에서)는 대부분 무시되었다.

2진수 순서에 대한 무작위성의 실제적인 척도는 많다.여기에는 통계적 시험, 변환 및 복잡성에 기반한 측정 또는 이러한 측정의 혼합이 포함된다.잘 알려져 있고 널리 사용되는 테스트 모음은 마르사글리아에 의해 도입된 테스트의 다이하드 배터리였다; 이것은 L'Ecuyer와 Simard에 의해 테스트U01 제품군으로 확장되었다.무작위성을 측정하기 위한 하다마드 변환의 사용은 S. Kak에 의해 제안되었고 필립스, 유엔, 홉킨스, 베스와 다이, 먼드, 그리고 마르사글리아와 자만에 의해 더 발전되었다.[6]

선형의 복잡성을 갖는 이러한 시험들 중 몇 가지는 무작위성의 스펙트럼 측도를 제공한다.T. 베스와 Z-D.Dai는 Kolmogorov 복잡성과 선형 복잡성은 [7]Y이긴 하지만 실질적으로 동일하다는 것을 보여주는 것이라고 주장했다.왕씨는 나중에 그들의 주장이 틀렸다는 것을 보여주었다.[8]그럼에도 불구하고 왕 교수는 마틴 뢰프 무작위 시퀀스의 경우 콜모고로프 복잡성은 본질적으로 선형 복잡성과 동일하다는 것을 증명했다.

이러한 실제적인 테스트는 문자열의 무작위성을 비교하는 것을 가능하게 한다.확률론적 근거에서 주어진 길이의 모든 문자열은 동일한 무작위성을 갖는다.그러나 다른 문자열들은 다른 Kolmogorov 복잡성을 가지고 있다.예를 들어, 다음 두 문자열을 고려하십시오.

문자열 1:
문자열 2:

문자열 1은 짧은 언어적 설명을 인정한다: "01의 32회 반복".이 설명은 22자를 가지고 있으며, 어떤 기본 시퀀스로부터 효율적으로 구성될 수 있다.[clarification needed]문자열 2는 64자로 되어 있는 문자열 자체를 적는 것 외에 뚜렷한 간단한 설명이 없으며,[clarification needed] 비교적으로 효율적인 기본 함수 표현도 없다.선형 하다마드 스펙트럼 시험(하다마드 변환 참조)을 사용하여, 이러한 시퀀스 중 첫 번째 시퀀스는 직관에 동의하는 두 번째 시퀀스보다 훨씬 덜 랜덤하다는 것을 알게 될 것이다.

주목할 만한 소프트웨어 구현

  • 다이하드
  • 테스트U01
  • 포밀랍에서 효용을 얻다.
  • NIST 통계 테스트 제품군(특별 간행물 800-22 개정판 1a)

참고 항목

메모들

  1. ^ Wolfram, Stephen (2002). A New Kind of Science. Wolfram Media, Inc. pp. 975–976. ISBN 978-1-57955-008-0.
  2. ^ Willi Meier; Othmar Staffelbach (1991), "Analysis of pseudo random sequences generated by cellular automata", Advances in Cryptology: Proc. Workshop on the Theory and Application of Cryptographic Techniques, EUROCRYPT '91. Lecture Notes in Computer Science 547: 186
  3. ^ Moshe Sipper; Marco Tomassini (1996), "Generating parallel random number generators by cellular programming", International Journal of Modern Physics C, 7 (2): 181–190, CiteSeerX 10.1.1.21.870, doi:10.1142/S012918319600017X.
  4. ^ 왕융게.(Pseudo) 랜덤 생성기의 LIL 테스트 및 일부 실험 결과에 관한 연구, http://webpages.uncc.edu/yonwang/, 2014
  5. ^ Yongge Wang; Tony Nicol (2014), "Statistical Properties of Pseudo Random Sequences and Experiments with PHP and Debian OpenSSL", Esorics 2014, Lncs 8712: 454–471
  6. ^ 테리 리터, "랜덤스 테스트: 문헌 조사", 웹 페이지: CBR-rand.
  7. ^ 베스, T, Z-D.1989년 다이.의사 랜덤 시퀀스의 복잡성 - 또는: 시퀀스를 설명할 수 있다면 랜덤일 수 없다.암호학의 발전 - 유로크립트 89. 533-543.스프링거-베를라그
  8. ^ 용게왕 1999.선형 복잡성 대 유사성: 베스와 다이 결과.In: Proc.99쪽 288쪽 298쪽LNCS 1716, Springer Verlag

외부 링크