다이하르트 시험

Diehard tests

다이하드 시험은 난수 발생기의 품질을 측정하기 위한 통계 시험의 배터리다.그것들은 조지 마르사글리아에 의해 수년에 걸쳐 개발되었고 1995년에 무작위 숫자의 CD-ROM으로 처음 출판되었다.[1]

테스트 개요

생일 스페이스
큰 간격의 랜덤 점을 선택하십시오.점 사이의 간격은 점증상 기하급수적으로 분포되어야 한다.[2]그 이름은 생일 역설의 바탕에 있다.
겹순열
연속된 5개의 난수 시퀀스를 분석한다.120개의 가능한 순서는 통계적으로 동일한 확률로 이루어져야 한다.
행렬의 순위
{0,1}에 걸쳐 행렬을 형성할 일부 랜덤 숫자에서 일부 비트를 선택한 다음 행렬의 순위를 결정하십시오.대열을 세다.
원숭이 시험
일부 비트 시퀀스를 "words"로 처리하십시오.겹치는 단어들을 개울에 세어라.나타나지 않는 "단어"의 수는 알려진 분포를 따라야 한다.그 이름은 무한 원숭이 정리에 바탕을 두고 있다.
1을 세어라.
연속 바이트 또는 선택한 바이트 각각에 1비트를 세십시오.카운트를 "문자"로 변환하고 5자 "단어"가 발생하는지 계산하십시오.
주차장 시험
100×100 정사각형에 단위 원을 랜덤하게 배치한다.원이 성공적으로 주차된 기존 원과 겹치지 않으면 성공적으로 주차된다.12,000번의 시도 후 성공적으로 주차된 원의 수는 일정한 정규 분포를 따라야 한다.
최소 거리 시험
10000×10000 정사각형에 8000개의 점을 랜덤하게 배치한 다음, 쌍 사이의 최소 거리를 구한다.이 거리의 제곱은 일정한 평균을 가지고 기하급수적으로 분포되어야 한다.
무작위 구검법
모서리 1000의 입방체에서 임의로 4000개의 점을 선택한다.구를 각 점의 중심에 배치하고, 그 반경은 다른 점까지의 최소 거리가 된다.가장 작은 구의 부피는 일정한 평균을 가지고 기하급수적으로 분포되어야 한다.
압착 시험
1이31 될 때까지 2를 (0,1)에 임의의 부동액으로 곱한다.이것을 100,000번 반복한다.1에 도달하는 데 필요한 부유물의 수는 일정한 분포를 따라야 한다.
중복합산검사
(0,1)에 대한 긴 연속 랜덤 플로트를 생성한다.100개의 연속된 부동액 시퀀스를 추가한다.합계는 특성 평균과 분산을 사용하여 정규 분포를 따라야 한다.
실행 테스트
(0,1)에 대한 긴 연속 랜덤 플로트를 생성한다.오름차순 및 내림차순 런을 카운트하십시오.계수는 일정한 분포를 따라야 한다.
크랩스 테스트
20만게임의 크랩을 하면서 게임당 승수와 투구수를 세어보자.각 카운트는 일정한 분포를 따라야 한다.

테스트 설명

생일 스페이스 테스트
1년 중 n일 이내에 m 생일을 선택하라.생일 사이의 간격을 나열하십시오.j가 해당 리스트에서 두 번 이상 발생하는 값의 수인 경우, j는 증상이 없는 포아송-평균3 m / (4n)으로 분포한다.경험에 따르면 n은 포아송 분포와18 그 평균을 비교하기 위해 상당히 커야 한다.이 검정에서는 n = 2와24 m = 2를9 사용하므로 j에 대한 기본 분포는 λ = 226 / 227 = 2. 500 js의 표본을 추출하고 카이-제곱 적합도 검정은 p 값을 제공한다.첫 번째 테스트는 지정된 파일의 정수의 비트 1-24(왼쪽부터 계산)를 사용한다.그런 다음 파일을 닫고 다시 여십시오.다음으로 비트 2–25는 생일을 제공하는 데 사용되고, 그 다음 비트 9–32에 3–26 등을 사용한다.각 비트 세트는 p-값을 제공하며, 9개의 p-값은 KSTEST에 대한 표본을 제공한다.
중복된 5단계의 시험
이것은 OPERM5 시험이다.32비트 무작위 정수 100만 개의 시퀀스를 살펴본다.5개의 연속 정수의 각 집합은 120개의 상태 중 하나에 있을 수 있으며, 5개의 숫자 순서가 가능하다.따라서 5번째, 6번째, 7번째, ... 숫자는 각각 상태를 제공한다.수천 개의 상태 전환이 관찰됨에 따라, 누적 카운트는 각 상태의 발생 횟수로 이루어진다.120×120 공분산 행렬의 약한 역행렬에 있는 2차 형태는 120×120 공분산 행렬(99위)과 함께 120 셀 카운트가 지정된 (비례학적으로) 정규 분포에서 나왔다는 우도비 검정과 동등한 시험을 산출한다.이 버전은 1000000 정수를 두 번 사용한다.이 테스트는 풀리지 않은 버그를 통해 지속적으로 p-값이 불량해질 수 있다.[3]
31×31 행렬에 대한 이항 순위 검정
시험 시퀀스에서 31개의 무작위 정수의 가장 왼쪽 31비트는 필드 {0,1}에 걸쳐 31×31 이진 행렬을 형성하는 데 사용된다.계급이 결정되다.그 순위는 0부터 31까지가 될 수 있지만, 순위 < 28은 드물다. 그리고 그 카운트는 순위 28과 합쳐진다.등급은 그러한 무작위 행렬 4만 개에 대해 확인되며 카이-제곱 검정은 등급 31, 30, 29 및 ≤ 28에 대해 수행된다.
32×32 행렬에 대한 이항 순위 검정
무작위 32×32 이진 행렬이 형성되며, 각 행은 32비트 무작위 정수다.계급이 결정되다.그 순위는 0에서 32까지 될 수 있고, 29 미만의 순위는 드물며, 그 카운트는 29위 순위와 함께 통합된다.등급은 무작위 행렬 4만 개에 대해 확인되며, 카이 제곱 시험은 등급 32, 31, 30 및 ≤ 29에 대해 수행된다.
6×8 행렬에 대한 이항 순위 검정
테스트 중인 제너레이터에서 나오는 6개의 무작위 32비트 정수 각각에서 지정된 바이트를 선택하고, 그 결과 6바이트는 순위가 결정되는 6×8 이진 행렬을 형성한다.그 순위는 0부터 6까지가 될 수 있지만, 0, 1, 2, 3등급은 드물다. 그들의 카운트는 4등급과 합쳐진다.등급은 무작위 행렬 100,000개에 대해 확인되며, 순위 6, 5, ≤ 4에 대한 카운트에 대해 카이 사각 테스트를 수행한다.
비트스트림 테스트
테스트 중인 파일은 비트 스트림으로 간주된다.이들을 b1, b2, ...라고 불러라 0, 1의 두 개의 '문자'가 있는 알파벳을 생각하고, 비트 흐름을 20자 '단어'의 연속이라고 생각하여 겹친다.따라서 첫 번째 단어는 bb12...b이고20, 두 번째 단어는 bb23...b21 등등이다.비트스트림 테스트는 누락된 20자(20비트) 단어 수를21 두 개의 겹쳐진 20자 단어로 계산한다.20자로 된 단어 2개가20 있을 수 있다.221 + 19비트의 실제 랜덤 문자열의 경우, 누락된 단어 j의 수는 평균 141,909와 시그마 428로 정규 분포를 따라야 한다.따라서 (j-141909)/428은 균일한 [0,1) p 값으로 이어지는 표준 정상변동(z 점수)이어야 한다.시험이 스무 번 반복되다.
OPSO, OQSO 및 DNA 테스트
OPSO는 중첩-초점-점거를 의미한다.OPSO 테스트는 1024자 알파벳에서 2글자로 된 단어를 고려한다.각 문자는 테스트할 시퀀스의 32비트 정수에서 지정된 10비트로 결정된다.OPSO는 221(오버랩핑) 2글자(221 + 1 "키 입력"부터)를 생성하고 누락된 단어 수(전체 시퀀스에 나타나지 않는 2글자)를 카운트한다.이 카운트는 평균 141909, 시그마 290으로 정규 분포에 매우 가까워야 한다.따라서 (missingwrds-141909) / 290은 표준 정규 변수여야 한다.OPSO 테스트는 테스트 파일에서 한 번에 32비트를 가져오고 지정된 10개의 연속 비트를 사용한다.그런 다음 지정된 다음 10비트에 대해 파일을 재시작한다.OQSO는 겹침 쿼드러플-스파스-점거를 의미한다.시험 OQSO는 시험 파일에서 5 연속 비트의 지정된 문자열로 결정되며 32비트 무작위 정수로 간주되는 각 문자는 32자의 알파벳에서 4글자로 된 단어를 고려한다는 점을 제외하면 유사하다.두21 개의 4자 단어, (221 + 3 "키 입력")의 시퀀스에서 누락된 단어의 평균 수는 다시 141909이며, 시그마 = 295이다.평균은 이론에 근거한다; 시그마는 광범위한 시뮬레이션에서 나온다.DNA 테스트는 무작위 정수의 순서에서 두 개의 지정된 비트에 의해 결정되는 4글자 C, G, A,T의 알파벳을 고려한다.10글자 단어를 고려하므로 OPSO와 OQSO에서와 같이 2개의28 가능한 단어가 있으며, 2개의21 (오버랩핑) 10글자 문자열(221+9 "키 스트로크")에서 누락된 평균 수는 141909이다.표준 편차 시그마 = 339는 시뮬레이션에 의해 OQSO에 대해 결정되었다.(OPSO에 대한 시그마, 290은 시뮬레이션에 의해 결정되는 것이 아니라 (3개소에 대한) 참값이다.
바이트 스트림에 대한 카운트-the-1의 테스트
테스트 중인 파일을 바이트 스트림(32비트 정수당 4개)으로 간주하십시오.각 바이트는 1초부터 8초까지 포함할 수 있으며 확률 1, 8, 28, 56, 70, 56, 28, 8, 256에 1을 포함할 수 있다.이제 바이트 스트림에서 값 A, B, C, D, E를 각각 "글자"로 하는 5글자의 겹치는 문자열을 제공하도록 하자.문자는 바이트 0, 1, 2 항복 A, 3 항복 B, 4 항복 C, 5 항복 D 및 6, 7, 8 항복 E의 1초 수로 결정된다.따라서 우리는 타자기의 원숭이가 다양한 확률로 다섯 개의 키를 두드린다(37, 56, 70, 56, 37 over 256).5개의 가능한5 5글자가 있으며, 256,000개의 5글자 문자열에서 각 단어의 빈도에 카운트가 이루어진다.셀 카운트의 공분산 행렬의 약한 역행렬에 있는 2차 형태는 5자 및 4자 셀 카운트의 카운트에 대한 (OBS-EXP)/2EXP의 순진한 피어슨 합계의 차이인 끌쿼리 시험 Q5–Q4를 제공한다.
특정 바이트에 대한 카운트-the-1의 테스트
테스트 중인 파일을 32비트 정수의 스트림으로 간주하십시오.각 정수에서 특정 바이트가 선택된다. 예를 들어, 가장 왼쪽 비트 1부터 8까지입니다.각 바이트는 0에서 8 1초까지 포함할 수 있으며 확률 1, 8, 28, 56, 70, 56, 28, 8, 256에 1을 포함할 수 있다.이제 연속적인 정수의 지정된 바이트가 값 A, B, C, D, E를 취하는 각 "글자" 5글자의 문자열을 제공하도록 한다.그 바이트 0, 1 또는 2 → A, 3 → B, 4 → C, 5 → D, 6, 7, 8 → E의 숫자에 따라 글자가 결정된다.그래서 우리는 타자기에서 37, 56, 70, 56, 37, 256의 다양한 확률로 5개의 키를 치는 원숭이를 가지고 있다.5개의 가능한5 5글자가 있으며, 256,000개의 5글자 문자열에서 각 단어의 빈도에 카운트가 이루어진다.셀 카운트의 공분산 행렬의 약한 역행렬에 있는 2차 형식은 5자 및 4자 셀 카운트의 카운트에 대한 (OB - EXP)/2EXP의 순진한 Pearson 합계의 차이인 끌쿼리 시험 Q5 - Q4를 제공한다.
주차장 테스트
100면 정사각형에서, 무작위로 차를 "주차"한다 – 반지름 1의 원.그리고 나서 2차, 3차, 기타 등등, 매번 "귀에 따라" 주차하도록 해 보십시오.즉, 주차를 시도하면 이미 주차되어 있는 차량과 충돌이 발생할 경우 새로운 임의 위치에서 다시 시도하십시오.(경로 문제를 피하려면 자동차보다는 주차 헬리콥터를 고려하십시오.)각각의 시도는 충돌 또는 성공으로 이어지며, 후자는 이미 주차되어 있는 차량의 목록을 증가시킨다.n을 플롯하면 시도 횟수 대 k를 성공적으로 주차하면 완벽한 무작위 숫자 생성기가 제공하는 곡선과 유사해야 하는 곡선이 나온다.그러한 무작위 곡선의 동작에 대한 이론은 손이 닿지 않는 것처럼 보이며, 이러한 시험 배터리에 그래픽 디스플레이를 사용할 수 없기 때문에 무작위 실험의 단순한 특성화가 사용된다: k, n = 12000번의 시도 후 성공적으로 주차된 자동차의 수.시뮬레이션 결과 k는 시그마 21.9로 평균 3523을 나타내야 하며 정규 분포에 매우 근접해야 한다.따라서 (k - 3523) / 21.9는 균일한 변수로 변환되어 10의 표본을 바탕으로 KSTEST에 입력을 제공하는 표준 정규 변수여야 한다.
최소 거리 시험
10000면 제곱에서 n = 8000 랜덤 점을 100번 선택한다.(n2 - n) / 두 점 쌍 사이의 최소 거리인 d를 찾으십시오.점들이 진정으로 독립적인 균일하다면, d2, 최소 거리의 제곱은 평균 0.995로 기하급수적으로 분포되어야 한다(매우 근접해야 한다.따라서 1 - exp(-d2 / 0.995)는 [0,1)에서 균일해야 하며, 결과 100 값에 대한 KSTEST는 제곱의 무작위 점에 대한 균일성 검사의 역할을 한다.시험 번호 = 0모드 5가 인쇄되지만, KSTEST는 10000×10000 사각형에서 8,000 포인트의 100개의 무작위 선택 전체 세트를 기반으로 한다.
3D 구 테스트
모서리 1000의 큐브에서 4000개의 랜덤 점을 선택하십시오.각 지점에서 다음 가장 가까운 지점에 도달할 수 있을 만큼 큰 구를 중심에 둔다.그러면 그러한 가장 작은 구의 부피는 평균 120˚ / 3으로 기하급수적으로 분포한다.따라서 반경 제곱은 평균 30으로 지수적이다. (평균은 광범위한 시뮬레이션을 통해 얻음).3D 구 테스트는 20회 4000개의 구를 생성한다.각 최소 반지름 칸은 1 - exp(-r3 / 30)를 사용하여 균일한 변수에 도달한 다음 20 p-값에서 KSTEST가 수행된다.
압착 시험
임의의 정수는 [0,1]에 유니폼을 입히기 위해 띄워진다.k = 231 = 2147483648로 시작하여, 이 테스트는 감소 k = 천장(k×U)을 사용하여 k를 1로 줄이는 데 필요한 반복 횟수인 j를 찾아내고, 테스트 중인 파일의 부동 정수로 U를 제공한다.그러한 j는 10만 번 발견되며, 그 다음, j가 6, 7, ..., 47, ≥ 48인 횟수를 셀 주파수에 대한 카이-제곱 검사에 사용한다.
중복합계 검정
정수는 동일한 [0,1) 변수의 시퀀스 U(1), U(2), ...를 얻기 위해 띄워진다.그런 다음 겹치는 합계 S(1) = U(1) + ... + U(100), S(2) = U(2) + ... + U(101)가 형성된다.Ss는 특정 공분산 행렬로 사실상 정상이다.Ss의 선형 변환은 이들을 일련의 독립적인 표준 규범으로 변환하며, 이는 KSTEST에 대한 균일한 변수로 변환된다.10개의 KSTEST의 p-값은 여전히 또 다른 KSTEST를 받는다.
런 테스트
지정된 파일에서 32비트 정수를 부동하여 얻은 일련의 균일한 [0,1) 변수에서 런 업 및 런 다운을 카운트한다.이 예는 런이 계산되는 방법을 보여준다: 0.123, 0.357, 0.789, 0.425, 0.224, 0.416, 0.95에는 다음 값에 따라 길이 3의 업런, 길이 2의 다운런 및 (적어도) 2의 업런이 포함된다.런업 및 런다운에 대한 공분산 행렬은 잘 알려져 있으며, 공분산 행렬의 약한 역에서 2차 형태에 대한 카이-제곱 검정을 유도한다.런은 길이 10000의 시퀀스에 대해 카운트된다.이 일은 열 번 한다.그리고는 되풀이했다.
크랩스 테스트
크랩스 20만 게임을 하고, 각 경기 종료에 필요한 승수와 투구수를 찾아낸다.승수는 평균 20만p, 분산 20만p(1 - p)의 정상(매우 근접)이어야 하며, p = 244 / 495이다.경기를 완성하는 데 필요한 투구는 1부터 무한대까지 다양할 수 있지만, > 21 모두의 카운트는 21로 뭉친다.카이-제곱 검사는 행의 수 셀 카운트에 대해 시행된다.테스트 파일의 각 32비트 정수는 [0,1]에 부동하고 6을 곱하고 결과의 정수 부분을 1에 더하는 방식으로 주사위 던지기 값을 제공한다.

DIEHARD의 대부분의 테스트는 p-값을 반환하는데, 입력 파일에 진정으로 독립적인 랜덤 비트가 포함되어 있다면 [0,1)에서 이 값이 균일해야 한다.이러한 p-값은 p = F(X)로 구하며, 여기서 F는 표본 랜덤 변수 X - 종종 정규 분포의 가정된 분포다.그러나 그 가정된 F는 단지 점근법적인 근사치일 뿐이며, 이 근사치에서는 꼬리가 가장 안 맞을 것이다.따라서 0.0012 또는 0.9983과 같이 때때로 0 또는 1에 가까운 p-값으로 놀라서는 안 된다.비트 스트림이 정말로 크게 실패하면 0 또는 1에서 6개 이상의 ps를 얻게 된다.시험이 많으므로 p < 0.025 또는 p > 0.975가 RNG가 "0.05 수준에서 시험에 불합격했다"는 것을 의미할 가능성은 낮다.우리는 그러한 많은 사건들이 DEEHARD가 생성하는 수백 개의 사건들 중에서 발생하기를 기대한다. 심지어 난수 발생기가 완벽하다는 조건까지도.

참고 항목

메모들

  1. ^ "The Marsaglia Random Number CDROM including the Diehard Battery of Tests of Randomness". Florida State University. 1995. Archived from the original on 2016-01-25.
  2. ^ 1953년 레니, p194
  3. ^ "Robert G. Brown's General Tools Page". Archived from the original on 2017-07-03.

외부 링크