Random-Number-Generator
為什麼 mt19937 未能通過 NIST SP 800-22 中的通用測試？
更新：在@SqueamishOssifrage 和@PaulUzdak 的幫助下，我們發現我的 NIST SP 800-22 的通用測試有問題。所以這成為一個沒有實際意義的問題。
檢查這份報告。它似乎通過了所有測試，但通用測試的所有 p 值都落在前 10 個百分位。我已將生成器的種子設置為 1。這是我的
assess程序配置：$ ./assess 100000 G E N E R A T O R S E L E C T I O N ______________________________________ [0] Input File [1] Linear Congruential [2] Quadratic Congruential I [3] Quadratic Congruential II [4] Cubic Congruential [5] XOR [6] Modular Exponentiation [7] Blum-Blum-Shub [8] Micali-Schnorr [9] G Using SHA-1 Enter Choice: 0 User Prescribed Input File: mt19937-seed-1.dat S T A T I S T I C A L T E S T S _________________________________ [01] Frequency [02] Block Frequency [03] Cumulative Sums [04] Runs [05] Longest Run of Ones [06] Rank [07] Discrete Fourier Transform [08] Nonperiodic Template Matchings [09] Overlapping Template Matchings [10] Universal Statistical [11] Approximate Entropy [12] Random Excursions [13] Random Excursions Variant [14] Serial [15] Linear Complexity INSTRUCTIONS Enter 0 if you DO NOT want to apply all of the statistical tests to each sequence and 1 if you DO. Enter Choice: 1 P a r a m e t e r A d j u s t m e n t s ----------------------------------------- [1] Block Frequency Test - block length(M): 128 [2] NonOverlapping Template Test - block length(m): 9 [3] Overlapping Template Test - block length(m): 9 [4] Approximate Entropy Test - block length(m): 10 [5] Serial Test - block length(m): 16 [6] Linear Complexity Test - block length(M): 500 Select Test (0 to continue): 0 How many bitstreams? 10 Input File Format: [0] ASCII - A sequence of ASCII 0's and 1's [1] Binary - Each byte in data file contains 8 bits of data Select input mode: 1 Statistical Testing In Progress......... Statistical Testing Complete!!!!!!!!!!!! $我使用樣本大小 100000 的原因是因為 NIST SP 800-22 提到它是一個可能的大小。（另見附錄 E，第 121 頁：“
$$ d $$在測試階段，NIST 通常按順序評估序列 $ 10^6 $ .") 我不知道理想的尺寸是多少。
------------------------------------------------------------------------------ RESULTS FOR THE UNIFORMITY OF P-VALUES AND THE PROPORTION OF PASSING SEQUENCES ------------------------------------------------------------------------------ generator is <mt19937-seed-1.dat> ------------------------------------------------------------------------------ C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 P-VALUE PROPORTION STATISTICAL TEST ------------------------------------------------------------------------------ 2 1 1 0 3 0 0 1 1 1 0.534146 10/10 Frequency 4 1 1 0 1 0 0 1 0 2 0.122325 9/10 BlockFrequency 1 2 1 0 1 1 1 1 2 0 0.911413 10/10 CumulativeSums 2 0 1 0 2 0 2 1 2 0 0.534146 10/10 CumulativeSums 1 1 4 0 0 0 2 1 1 0 0.122325 10/10 Runs 1 2 1 1 0 2 1 0 0 2 0.739918 10/10 LongestRun 1 1 1 0 1 2 0 1 2 1 0.911413 10/10 Rank 0 1 0 2 1 1 1 0 3 1 0.534146 10/10 FFT 2 0 2 0 1 0 1 2 1 1 0.739918 10/10 NonOverlappingTemplate 2 2 3 0 0 1 0 0 1 1 0.350485 10/10 NonOverlappingTemplate 0 1 3 1 1 1 0 1 1 1 0.739918 10/10 NonOverlappingTemplate 3 1 0 2 1 1 0 0 1 1 0.534146 10/10 NonOverlappingTemplate 1 2 1 1 1 1 2 0 1 0 0.911413 10/10 NonOverlappingTemplate 1 2 0 2 1 0 0 2 1 1 0.739918 10/10 NonOverlappingTemplate 1 2 0 0 2 2 0 1 1 1 0.739918 10/10 NonOverlappingTemplate 1 1 3 0 0 2 2 0 0 1 0.350485 10/10 NonOverlappingTemplate 0 1 0 2 2 1 1 1 1 1 0.911413 10/10 NonOverlappingTemplate 1 1 0 0 0 1 2 1 1 3 0.534146 10/10 NonOverlappingTemplate 1 0 1 1 2 2 0 1 1 1 0.911413 10/10 NonOverlappingTemplate 1 1 0 3 0 0 2 0 1 2 0.350485 9/10 NonOverlappingTemplate 2 0 1 1 2 1 2 0 1 0 0.739918 10/10 NonOverlappingTemplate 0 3 1 1 2 1 1 0 0 1 0.534146 10/10 NonOverlappingTemplate 0 0 2 2 1 3 1 1 0 0 0.350485 10/10 NonOverlappingTemplate 3 0 1 0 1 3 2 0 0 0 0.122325 10/10 NonOverlappingTemplate 0 0 1 2 2 1 1 2 0 1 0.739918 10/10 NonOverlappingTemplate 1 0 3 1 0 0 2 1 1 1 0.534146 10/10 NonOverlappingTemplate 1 0 1 3 1 1 1 1 1 0 0.739918 10/10 NonOverlappingTemplate 2 1 2 0 0 0 0 3 1 1 0.350485 10/10 NonOverlappingTemplate 2 0 0 1 0 1 2 3 1 0 0.350485 9/10 NonOverlappingTemplate 0 1 1 1 0 0 0 4 1 2 0.122325 10/10 NonOverlappingTemplate 0 3 2 1 1 0 1 1 1 0 0.534146 10/10 NonOverlappingTemplate 1 0 0 0 3 0 2 1 3 0 0.122325 10/10 NonOverlappingTemplate 3 1 0 0 2 0 0 2 1 1 0.350485 9/10 NonOverlappingTemplate 0 1 2 1 0 0 3 2 0 1 0.350485 10/10 NonOverlappingTemplate 0 1 2 1 0 0 2 1 1 2 0.739918 10/10 NonOverlappingTemplate 0 1 1 1 0 1 1 1 2 2 0.911413 10/10 NonOverlappingTemplate 2 2 0 0 0 1 2 2 0 1 0.534146 10/10 NonOverlappingTemplate 1 1 0 2 0 1 0 0 2 3 0.350485 10/10 NonOverlappingTemplate 1 2 0 1 0 0 1 3 2 0 0.350485 10/10 NonOverlappingTemplate 1 1 1 0 0 2 2 2 1 0 0.739918 10/10 NonOverlappingTemplate 1 0 2 1 2 0 2 0 0 2 0.534146 10/10 NonOverlappingTemplate 0 2 1 1 0 1 0 3 0 2 0.350485 10/10 NonOverlappingTemplate 0 1 1 3 3 0 1 0 1 0 0.213309 10/10 NonOverlappingTemplate 0 3 1 0 1 2 0 0 2 1 0.350485 10/10 NonOverlappingTemplate 0 1 1 1 2 0 0 2 1 2 0.739918 10/10 NonOverlappingTemplate 1 1 3 1 1 0 0 1 1 1 0.739918 10/10 NonOverlappingTemplate 0 0 1 0 0 1 2 5 1 0 0.008879 10/10 NonOverlappingTemplate 1 1 0 1 1 1 1 3 0 1 0.739918 10/10 NonOverlappingTemplate 0 1 0 1 1 1 1 2 1 2 0.911413 10/10 NonOverlappingTemplate 1 1 1 0 0 1 1 2 2 1 0.911413 10/10 NonOverlappingTemplate 0 1 1 2 1 1 2 0 1 1 0.911413 10/10 NonOverlappingTemplate 0 1 0 2 1 1 3 0 1 1 0.534146 10/10 NonOverlappingTemplate 1 1 2 2 0 3 0 0 1 0 0.350485 10/10 NonOverlappingTemplate 0 3 1 1 1 1 1 0 0 2 0.534146 10/10 NonOverlappingTemplate 1 2 1 1 0 1 2 2 0 0 0.739918 10/10 NonOverlappingTemplate 0 2 0 1 1 2 3 0 1 0 0.350485 10/10 NonOverlappingTemplate 1 1 1 1 1 0 1 1 1 2 0.991468 10/10 NonOverlappingTemplate 2 0 0 2 0 1 1 2 2 0 0.534146 10/10 NonOverlappingTemplate 1 1 3 0 0 0 4 0 0 1 0.035174 10/10 NonOverlappingTemplate 0 1 1 0 1 0 1 3 0 3 0.213309 10/10 NonOverlappingTemplate 2 1 0 0 2 0 2 1 1 1 0.739918 10/10 NonOverlappingTemplate 2 1 3 1 0 0 0 0 1 2 0.350485 10/10 NonOverlappingTemplate 0 2 1 1 1 2 1 0 2 0 0.739918 10/10 NonOverlappingTemplate 2 0 0 1 0 4 0 1 1 1 0.122325 10/10 NonOverlappingTemplate 1 2 1 0 0 1 2 1 2 0 0.739918 9/10 NonOverlappingTemplate 1 1 1 2 0 0 2 0 2 1 0.739918 10/10 NonOverlappingTemplate 1 1 3 1 0 1 0 1 2 0 0.534146 10/10 NonOverlappingTemplate 0 1 3 2 0 1 0 2 1 0 0.350485 10/10 NonOverlappingTemplate 0 1 0 1 0 3 2 2 0 1 0.350485 10/10 NonOverlappingTemplate 2 1 0 2 0 0 0 4 0 1 0.066882 10/10 NonOverlappingTemplate 0 1 2 1 1 2 0 1 0 2 0.739918 10/10 NonOverlappingTemplate 3 0 1 0 1 0 1 1 0 3 0.213309 10/10 NonOverlappingTemplate 1 1 1 1 1 2 1 0 2 0 0.911413 9/10 NonOverlappingTemplate 0 1 3 0 2 0 1 1 2 0 0.350485 10/10 NonOverlappingTemplate 1 1 1 0 2 0 1 0 2 2 0.739918 10/10 NonOverlappingTemplate 0 1 0 1 3 1 0 0 3 1 0.213309 10/10 NonOverlappingTemplate 2 2 2 0 0 2 0 0 0 2 0.350485 10/10 NonOverlappingTemplate 1 3 0 0 1 3 0 2 0 0 0.122325 9/10 NonOverlappingTemplate 1 1 0 0 2 1 0 1 3 1 0.534146 9/10 NonOverlappingTemplate 0 1 0 2 1 1 2 0 1 2 0.739918 10/10 NonOverlappingTemplate 0 0 1 1 0 1 0 1 3 3 0.213309 10/10 NonOverlappingTemplate 0 0 3 3 0 0 1 1 2 0 0.122325 10/10 NonOverlappingTemplate 2 0 2 0 1 0 1 2 1 1 0.739918 10/10 NonOverlappingTemplate 0 0 3 0 2 0 0 2 2 1 0.213309 10/10 NonOverlappingTemplate 2 3 0 1 1 1 2 0 0 0 0.350485 10/10 NonOverlappingTemplate 1 1 1 0 3 1 0 1 0 2 0.534146 10/10 NonOverlappingTemplate 1 0 1 1 1 1 2 2 0 1 0.911413 10/10 NonOverlappingTemplate 0 1 0 0 1 3 1 0 2 2 0.350485 10/10 NonOverlappingTemplate 2 1 3 0 0 0 2 1 1 0 0.350485 9/10 NonOverlappingTemplate 0 0 2 1 2 2 0 0 0 3 0.213309 10/10 NonOverlappingTemplate 2 2 0 1 0 1 1 1 2 0 0.739918 10/10 NonOverlappingTemplate 0 1 1 1 0 3 1 0 0 3 0.213309 10/10 NonOverlappingTemplate 2 0 2 1 2 1 1 0 1 0 0.739918 10/10 NonOverlappingTemplate 2 2 0 1 2 1 0 0 2 0 0.534146 9/10 NonOverlappingTemplate 2 0 1 1 2 1 2 0 0 1 0.739918 10/10 NonOverlappingTemplate 1 1 0 2 0 3 2 1 0 0 0.350485 10/10 NonOverlappingTemplate 2 0 1 1 1 1 0 2 1 1 0.911413 10/10 NonOverlappingTemplate 0 1 1 2 2 0 1 0 1 2 0.739918 10/10 NonOverlappingTemplate 0 1 2 1 0 3 0 2 1 0 0.350485 10/10 NonOverlappingTemplate 1 1 2 0 2 1 2 0 0 1 0.739918 10/10 NonOverlappingTemplate 0 3 0 0 2 0 1 3 0 1 0.122325 10/10 NonOverlappingTemplate 1 0 0 1 3 1 2 1 1 0 0.534146 10/10 NonOverlappingTemplate 0 0 0 1 1 2 0 0 2 4 0.066882 10/10 NonOverlappingTemplate 1 1 0 2 1 2 1 1 1 0 0.911413 10/10 NonOverlappingTemplate 0 0 1 0 1 2 3 1 2 0 0.350485 10/10 NonOverlappingTemplate 1 4 1 0 1 0 0 0 3 0 0.035174 10/10 NonOverlappingTemplate 1 1 2 3 0 0 0 0 2 1 0.350485 10/10 NonOverlappingTemplate 1 1 0 1 2 2 2 0 1 0 0.739918 10/10 NonOverlappingTemplate 0 1 1 1 3 1 1 0 1 1 0.739918 10/10 NonOverlappingTemplate 1 0 2 0 2 1 0 1 3 0 0.350485 10/10 NonOverlappingTemplate 1 1 0 1 0 0 4 2 1 0 0.122325 9/10 NonOverlappingTemplate 2 2 1 0 3 0 1 1 0 0 0.350485 10/10 NonOverlappingTemplate 2 1 2 2 0 0 1 1 0 1 0.739918 9/10 NonOverlappingTemplate 1 0 0 1 2 2 0 0 2 2 0.534146 10/10 NonOverlappingTemplate 1 2 1 2 1 1 0 0 1 1 0.911413 9/10 NonOverlappingTemplate 2 1 0 2 0 1 3 0 1 0 0.350485 9/10 NonOverlappingTemplate 2 0 1 0 2 1 1 1 0 2 0.739918 10/10 NonOverlappingTemplate 3 2 2 0 1 0 0 0 1 1 0.350485 10/10 NonOverlappingTemplate 2 2 1 0 1 2 1 0 0 1 0.739918 10/10 NonOverlappingTemplate 1 0 2 1 1 2 2 1 0 0 0.739918 9/10 NonOverlappingTemplate 1 0 2 0 1 2 0 0 2 2 0.534146 10/10 NonOverlappingTemplate 1 2 0 0 0 1 2 2 1 1 0.739918 10/10 NonOverlappingTemplate 0 1 1 1 1 0 1 2 2 1 0.911413 10/10 NonOverlappingTemplate 1 0 2 2 0 0 2 3 0 0 0.213309 10/10 NonOverlappingTemplate 1 3 0 0 0 0 2 2 0 2 0.213309 10/10 NonOverlappingTemplate 1 0 2 2 1 1 1 0 0 2 0.739918 10/10 NonOverlappingTemplate 0 3 0 0 1 1 1 1 1 2 0.534146 10/10 NonOverlappingTemplate 1 0 1 3 0 1 2 1 0 1 0.534146 10/10 NonOverlappingTemplate 1 0 0 1 1 4 1 1 1 0 0.213309 10/10 NonOverlappingTemplate 2 0 2 0 2 0 1 1 2 0 0.534146 10/10 NonOverlappingTemplate 1 0 3 0 0 1 0 2 0 3 0.122325 10/10 NonOverlappingTemplate 2 0 2 1 0 1 1 1 1 1 0.911413 10/10 NonOverlappingTemplate 1 4 1 1 1 0 0 1 1 0 0.213309 9/10 NonOverlappingTemplate 2 1 1 1 2 0 1 0 1 1 0.911413 10/10 NonOverlappingTemplate 1 0 0 1 0 5 0 2 0 1 0.008879 10/10 NonOverlappingTemplate 1 1 0 2 1 0 1 0 4 0 0.122325 10/10 NonOverlappingTemplate 1 1 1 2 1 1 1 1 0 1 0.991468 10/10 NonOverlappingTemplate 3 3 0 0 2 0 1 0 0 1 0.122325 10/10 NonOverlappingTemplate 0 0 1 2 1 3 2 0 0 1 0.350485 10/10 NonOverlappingTemplate 1 4 0 0 0 0 1 2 0 2 0.066882 10/10 NonOverlappingTemplate 1 1 0 1 4 1 1 0 0 1 0.213309 10/10 NonOverlappingTemplate 2 0 1 0 1 0 1 2 2 1 0.739918 9/10 NonOverlappingTemplate 0 1 1 2 1 1 1 2 0 1 0.911413 10/10 NonOverlappingTemplate 0 1 1 2 1 2 1 1 1 0 0.911413 10/10 NonOverlappingTemplate 2 2 0 0 1 1 4 0 0 0 0.066882 9/10 NonOverlappingTemplate 1 1 0 1 2 3 0 1 1 0 0.534146 10/10 NonOverlappingTemplate 2 0 0 2 0 1 1 1 1 2 0.739918 10/10 NonOverlappingTemplate 2 1 0 0 2 1 0 2 1 1 0.739918 10/10 NonOverlappingTemplate 3 0 0 0 0 1 2 1 2 1 0.350485 10/10 NonOverlappingTemplate 0 1 3 0 1 1 0 1 2 1 0.534146 10/10 NonOverlappingTemplate 2 1 0 0 0 1 5 0 1 0 0.008879 10/10 NonOverlappingTemplate 1 2 1 1 2 0 2 0 1 0 0.739918 10/10 NonOverlappingTemplate 4 1 2 1 0 0 1 1 0 0 0.122325 9/10 NonOverlappingTemplate 2 0 1 2 1 1 0 1 0 2 0.739918 10/10 NonOverlappingTemplate 1 2 0 2 0 2 1 1 0 1 0.739918 10/10 NonOverlappingTemplate 0 0 3 3 0 0 1 1 2 0 0.122325 10/10 NonOverlappingTemplate 1 1 2 0 2 0 2 1 1 0 0.739918 10/10 OverlappingTemplate 10 0 0 0 0 0 0 0 0 0 0.000000 * 0/10 * Universal 1 0 1 1 2 2 3 0 0 0 0.350485 10/10 ApproximateEntropy 1 0 0 0 0 0 0 0 0 0 ---- 1/1 RandomExcursions 0 0 0 0 0 0 1 0 0 0 ---- 1/1 RandomExcursions 0 0 1 0 0 0 0 0 0 0 ---- 1/1 RandomExcursions 0 0 0 0 0 0 1 0 0 0 ---- 1/1 RandomExcursions 1 0 0 0 0 0 0 0 0 0 ---- 1/1 RandomExcursions 1 0 0 0 0 0 0 0 0 0 ---- 1/1 RandomExcursions 1 0 0 0 0 0 0 0 0 0 ---- 1/1 RandomExcursions 0 0 0 0 1 0 0 0 0 0 ---- 1/1 RandomExcursions 0 0 0 1 0 0 0 0 0 0 ---- 1/1 RandomExcursionsVariant 0 0 0 0 1 0 0 0 0 0 ---- 1/1 RandomExcursionsVariant 0 0 0 0 0 1 0 0 0 0 ---- 1/1 RandomExcursionsVariant 0 0 0 0 0 0 0 1 0 0 ---- 1/1 RandomExcursionsVariant 0 0 0 0 0 0 0 0 0 1 ---- 1/1 RandomExcursionsVariant 0 0 0 0 0 1 0 0 0 0 ---- 1/1 RandomExcursionsVariant 0 1 0 0 0 0 0 0 0 0 ---- 1/1 RandomExcursionsVariant 1 0 0 0 0 0 0 0 0 0 ---- 1/1 RandomExcursionsVariant 0 1 0 0 0 0 0 0 0 0 ---- 1/1 RandomExcursionsVariant 0 1 0 0 0 0 0 0 0 0 ---- 1/1 RandomExcursionsVariant 0 0 1 0 0 0 0 0 0 0 ---- 1/1 RandomExcursionsVariant 0 0 0 0 0 0 1 0 0 0 ---- 1/1 RandomExcursionsVariant 0 0 0 0 0 0 0 0 1 0 ---- 1/1 RandomExcursionsVariant 0 0 0 0 1 0 0 0 0 0 ---- 1/1 RandomExcursionsVariant 0 0 0 0 1 0 0 0 0 0 ---- 1/1 RandomExcursionsVariant 0 0 0 0 0 1 0 0 0 0 ---- 1/1 RandomExcursionsVariant 0 0 0 0 0 0 1 0 0 0 ---- 1/1 RandomExcursionsVariant 0 0 0 0 0 0 0 1 0 0 ---- 1/1 RandomExcursionsVariant 0 3 0 1 1 0 3 0 0 2 0.122325 10/10 Serial 1 1 0 0 2 1 1 1 2 1 0.911413 10/10 Serial 0 1 1 1 0 2 1 3 0 1 0.534146 10/10 LinearComplexity包含數據的文件是一個二進製文件，其中包含
mt19937以 little-endian 格式輸出的所有數字。它是由這個程序產生的#include <random> #include <stdio.h> using namespace std; int main() { unsigned int n; std::minstd_rand0 generator(1); for (;;) { n = generator(); fwrite(&n, sizeof n, 1, stdout); } return 0; }例如，您可以執行
$ ./cppmt19937 > mt19937-seed-1.dat並在幾秒鐘後中斷它。它會產生幾兆字節的數據。
為什麼通用測試在這裡做得這麼好？（FWIW，發電機也是
ranlux48如此。）
關於 MT 作為密鑰流生成器的已知弱點，另一個答案是正確的。
Maurer 設計了他的測試，方法是評估具有有限記憶體的遍歷（比 iid 更通用）二進制源中二進制視窗重複時間的樣本平均值，並僅基於輸出的這些特徵計算源熵的估計的密鑰流。因此，他的測試是一個通用熵率估計器。
因此，他的目標不是特定缺陷，而是結構缺陷。
請參閱他論文第 10-11 頁的討論。後來，Coron 在他的論文中使用的 Maurer 公式中發現了一個錯誤，請參見此處。據推測，NIST 測試已經考慮了這一修正。
恐怕您的測試在某個地方是錯誤的。
MT 在全世界範圍內使用，對大多數科學家來說已經足夠了。是的，它不是加密的，並且在更高維度上有一些非常小的缺陷。但是 NIST 通用測試沒有機會獲得這一點。如果簡單的約 100 行程式碼
universal.c可以使 Twister 失效，那麼沒有人會使用它。正如我根據 NIST 800-90b, § 5.1 通過排列測試確定的那樣，它的輸出中的相關性為零。我使用
snappy了 , lzma, bz2 和 zlib 算法。cmix（世界上最強大的壓縮器之一）無法壓縮它。請記住，Maurer 的測試畢竟是一個可壓縮性測試。但最重要的是，這是我在 NIST 通用測試中的輸出：------------------------------------------------------------------------------- RESULTS FOR THE UNIFORMITY OF P-VALUES AND THE PROPORTION OF PASSING SEQUENCES ------------------------------------------------------------------------------ generator is </tmp/mt.bin> ------------------------------------------------------------------------------ C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 P-VALUE PROPORTION STATISTICAL TEST ------------------------------------------------------------------------------ 1 2 1 0 2 1 0 0 1 2 0.739918 10/10 Universal - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - The minimum pass rate for each statistical test with the exception of the random excursion (variant) test is approximately = 8 for a sample size = 10 binary sequences.Twister 獲得了 10MB 的樣本。然後我們必須得出結論，鑑於所有支持 Twister 的證據，測試方法出了問題。您的線路：-
10 0 0 0 0 0 0 0 0 0 0.000000 * 0/10 * Universal ^^一端為 10 表示非常鬆散的 P 分佈和巨大的測試失敗。這種偶然發生的機率實際上是 0.000000。