基于泊松对相关的伪随机数发生器的统计测试方法

On Testing Pseudo Random Generators Via Statistical Tests Based on the Poissonian Pair Correlations

测试伪随机数发生器(pseudo random number generator,PRNG)的性能是一个非常重要的问题,通常以能否通过检验均匀性和独立性的统计测试方法来衡量.1998年Rudnick和Sarnak提出了[0,1)上实数序列的泊松对相关(Poissonian pair correlations,PPC)的概念,独立且均匀分布的实数序列满足泊松对相关.该文基于泊松对相关的概念提出了一种测试(0,1)中伪随机数序列的一级统计测试方法,给出了收敛判别标准的选取方法,并对常见的PRNG(线性同余发生器、Mersenne Twister、Matlab.rand函数以及基于无理数π重叠产生的PRNG等)进行了测试,同时与卡方检验、序列检验、游程检验以及自相关检验进行比较.结果表明该测试方法不仅简单灵活、可操作性和可移植性较强,能有效地同时检验伪随机数序列的均匀性和独立性.

Testing the quality of pseudo random number generators is an important issue.In general,PRNGs’randomness is measured by whether it passes the statistical test of testing uniformity and independence.In 1998,Rudnick and Sarnak proposed the concept of Poissonian pair correlations of real number sequences in[0,1),an i.i.d.random sequence(sampled from the uniform distribution in(0,1))has Poissonian pair correlations.In this paper we propose a single-level statistical test for the real number sequences in(0,1)based on the Poissonian pair correlations.We carried out PPC test on common PRNGs(Linear Congruential Generators,Mersenne Twister,Matlab.rand function,and PRNG based on the overlap of irrational numbersπ,etc),introducing the selection method of convergence criterion.The test results show that the statistical test can effectively test the uniformity and independence of the pseudo-random number sequence at the same time.