[信息与通信]NIST随机数测试标准.pdf

NIST 随机数测试 （李璞编译） 本文是根据 NIST 官方网站的说明书编译而成，仅为 学术交流之用，请勿用作它途。如转载请注明出处！ 另因水平有限，欢迎批评指正。 联系方式： Email ：lipu8603@126.com Address ：太原理工大学光电工程研究所 引言： 这套 NIST （国家标准与技术研究所）测试程序是一个统计包，包括16 种测试手 段。这些测试手段可测试由用作必威体育官网网址随机或者伪随机数发生器的硬件和软件产生 的任意长的2 进制序列的随机性。这些测试手段主要致力于判定可能存在于序列 中的多种多样的非随机性。其中一些测试又可以分解成多种子测验。这 16 种测 试手段是： 1. 频率检验， 2. 块内频数检验， 3. 游程检验， 4. 块内最长游程检验， 5. 二元矩阵秩检验， 6. 离散傅里叶变换检验， 7. 非重叠模块匹配检验， 8. 重叠模块匹配检验， 9. Maurer 的通用统计检验， 10. Lempel-Ziv 压缩检验， 11. 线性复杂度检验， 12. 序列检验， 13. 近似熵检验， 14. 累加和检验， 15. 随机游动检验， 16. 随机游动状态频数检验。 以下分别介绍这 16 种检测手段，这里须注意，下面讲到的很多例子里面的小样 本仅仅是为了作示例性的说明，比如说，n=10 。这个正态近似值并不适用于这些 例子。 2.1 频数（一位）检验 2.1.1 检验目的 该检验主要是看 0 和 1 在整个序列中所占的比例。检验的目的是确定序列中的 1 和 0 数是否与真正的随机 序列中的 1 和 0 数近似相同。检验评定 1 码占 1/2，也就是说，在整个序列中 0 和 1 的数目是一样的。其余 别的检验手段都是在该检验成立的基础上进行的，并且没有任何证据表明被测序列是不随机的。 2.1.2 函数调用 Frequency （n ）， 这里 n 表示一串二进制序列的长度。 函数中用的其余的参数来源于待检验的码：      表示一串随机或者伪随机码序列，即 = 1 ， 2 ，… ， n 。 2.1.3 检验统计量和参照分布 sobs : Xi 和的绝对值除以序列的长度，其中Xi = 2e - 1 = 。 检验统计量的标准分布是半正态分布（当n很大时）。（注意：如果z （z sobs /2 ）服从正态分布，那么|z | 就服从半正态分布。）如果序列是随机的，那么正负趋于互相抵消，这样检验统计量将约等于。如果