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

摘要/Abstract

摘要：

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

关键词: 泊松对相关, 伪随机数发生器, 统计测试方法, 一级测试

Abstract:

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 $\pi$, 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.

Key words: Poissonian Pair Correlations, Pseudo Random Number Generators, Statistical test, Single-level testing

中图分类号:

O213.9

叶笑,丁义明. 基于泊松对相关的伪随机数发生器的统计测试方法[J]. 数学物理学报, 2022, 42(5): 1482-1495.

Xiao Ye,Yiming Ding. On Testing Pseudo Random Generators Via Statistical Tests Based on the Poissonian Pair Correlations[J]. Acta mathematica scientia,Series A, 2022, 42(5): 1482-1495.

图/表 7

图 1

图 2

图 3

图 4

表 1

图 5

表 2

参考文献 27

1	Marsaglia G. The structure of linear congruential sequences//Applications of number theory to numerical analysis. Academic Press, 1972: 249–285
2	L'Ecuyer P. Testing random number generators//Proceedings of the 24th Conference on Winter Simulation(WSC'92). Association for Computing Machinery, 1992: 305–313
3	Pareschi F, Rovatti R, Setti G. Second-level NIST randomness tests for improving test reliability//2007 IEEE International Symposium on Circuits and Systems. IEEE, 2007: 1437–1440
4	Brown R G, Eddelbuettel D, Bauer D. Dieharder. Durham: Duke University Physics Department, 2018: 9–128
5	L'Ecuyer P , Simard R . TestU01: A C library for empirical testing of random number generators. ACM Transactions on Mathematical Software, 2007, 33 (4): 1- 40 doi: 10.1145/1268776.1268777
6	Rukhin A, Soto J, Nechvatal J, et al. A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications//NIST Special Publication 800-22 Revision 1a. Gaithersburg: National Institute of Standards and Technology, 2010
7	Machicao J , Ngo Q Q , Molchanov V , et al. A visual analysis method of randomness for classifying and ranking pseudo-random number generators. Information Sciences, 2021, 558 (3): 1- 20
8	Lorek P , Ƚoś G , Gotfryd K , et al. On testing pseudorandom generators via statistical tests based on the arcsine law. Journal of Computational and Applied Mathematics, 2020, 380 (1): 1- 17
9	L'Ecuyer P, Simard R. A software library in ANSI C for empirical testing of random number generators. Département d'Informatique et de Recherche Opérationnelle Université de Montreal, 2013: 88–90
10	Wang Y , Nicol T . On statistical distance based testing of pseudo random sequences and experiments with PHP and Debian OpenSSL. Computers and Security, 2015, 53 (9): 44- 64
11	Rudnick Z , Sarnak P . The pair correlation function of fractional parts of polynomials. Communications in mathematical physics, 1998, 194 (1): 61- 70 doi: 10.1007/s002200050348
12	Larcher G , Grepstad S . On pair correlation and discrepancy. Archiv der Mathematik, 2017, 109 (2): 143- 149 doi: 10.1007/s00013-017-1060-1
13	Asmussen S , Glynn P W .Stochastic Simulation: Algorithms and Analysis.版本New York:Springer,2007:30-48
14	Matsumoto M , Nishimura T . Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator. ACM Transactions on Modeling and Computer Simulation, 1998, 8 (1): 3- 30 doi: 10.1145/272991.272995
15	L'Ecuyer P , Blouin F , Couture R . A search for good multiple recursive random number generators. ACM Transactions on Modeling and Computer Simulation, 1993, 3 (2): 87- 98 doi: 10.1145/169702.169698
16	Steinerberger S . Localized quantitative criteria for equidistribution. Acta Arithmetica, 2017, 180 (2): 183- 199 doi: 10.4064/aa170410-22-5
17	Aistleitner C , Lachmann T , Pausinger F . Pair correlations and equidistribution. Journal of Number Theory, 2018, 182 (1): 206- 220
18	Aistleitner C , El-Baz D , Munsch M . A pair correlation problem, and counting lattice points with the zeta function. Geometric and Functional Analysis, 2021, 31 (3): 483- 512 doi: 10.1007/s00039-021-00564-6
19	Marklof J . Pair correlation and equidistribution on manifolds. Monatshefte für Mathematik, 2020, 191 (2): 279- 294 doi: 10.1007/s00605-019-01308-3
20	Larcher G, Stockinger W. Pair correlation of sequences with maximal additive energy//Mathematical Proceedings of the Cambridge Philosophical Society. Cambridge University Press, 2020, 168(2): 287–293
21	Marklof J , Str?mbergsson A . Equidistribution of Kronecker sequences along closed horocycles. Geometric and Functional Analysis, 2003, 13 (6): 1239- 1280 doi: 10.1007/s00039-003-0445-4
22	Aistleitner C , Baker S . On the pair correlations of powers of real numbers. Israel Journal of Mathematics, 2021, 242 (1): 243- 268
23	谭秋衡. 时间序列的非平稳性度量及其应用. 北京: 中国科学院研究生院, 2013谭秋衡. 时间序列的非平稳性度量及其应用. 北京: 中国科学院研究生院, 2013年
	Tan Q H. Non-stationary Measurement of Time Series and its Application. Beijing: Graduate School of Chinese Academy of Sciences, 2013
24	丁义明, 范文涛, 谭秋衡, 等. 数据流的非平稳性度量. 数学物理学报, 2010, 30A (5): 1364- 1376
	Ding Y M , Fan W T , Tan Q H , et al. Nonstationarity measure of data stream. Chinese Journal of Mathematical Physics, 2010, 30A (5): 1364- 1376
25	谭秋衡, 丁义明. 基于非平稳性度量的彩票数据实证分析. 数学物理学报, 2014, 34A (1): 207- 216
	Tan Q H , Ding Y M . Empirical analysis of lottery data based on non-stationarity measure. Chinese Journal of Mathematical Physics, 2014, 34A (1): 207- 216
26	张晶, 余旌胡. 线性回归模型参数估计方法的分辨率. 数学物理学报, 2020, 40A (5): 1381- 1392
	Zhang J , Yu J H . Parameter resolution of estimation methods for linear regression models. Chinese Journal of Mathematical Physics, 2020, 40A (5): 1381- 1392
27	吕洋, 丁义明, 谭秋衡. 基于非平稳性度量的数字印章信息匹配. 数学物理学报, 2021, 41A (3): 892- 901
	Lv Y , Ding Y M , Tan Q H . Electronic seal matching based on nonstationarity measure. Chinese Journal of Mathematical Physics, 2021, 41A (3): 892- 901

PRNG	$ P_{1} $	标准差	变异系数
LCG	0.9810	0.0314	0.0320
MT	0.9761	0.0438	0.0448
SPSS	0.9759	0.0435	0.0446
RANDU	0.9725	0.0478	0.0492
MRG	0.9717	0.0517	0.0532
Matlab	0.9713	0.0610	0.0628
Python	0.9704	0.0621	0.0640
Excel	0.9672	0.0808	0.0835
BBS	0.9647	0.0962	0.0998
$ \pi $	0.9453	0.1013	0.1072
$ \sqrt{n} $	0.1478	0.0287	0.1945

PRNG	$ P_{1} $	$ P_{2} $	$ P_{3} $	卡方检验	序列检验	游程检验	自相关检验
LCG	0.9810	0.9676	0.9230	99%	99%	98%	97%
MT	0.9761	0.9602	0.9167	100%	100%	99%	100%
SPSS	0.9759	0.9584	0.9173	98%	98%	99%	99%
RANDU	0.9725	0.9568	0.9162	100%	99%	94%	99%
MRG	0.9717	0.9557	0.9157	99%	98%	100%	100%
Matlab	0.9713	0.9504	0.9046	99%	98%	100%	100%
Python	0.9704	0.9541	0.9134	97%	98%	100%	100%
Excel	0.9672	0.9506	0.9116	100%	99%	99%	97%
BBS	0.9647	0.9479	0.9084	100%	100%	99%	100%
$ \pi $	0.9453	0.9209	0.8593	98%	0%	0%	100%
$ \sqrt{n} $	0.1478	0.1389	0.1229	100%	0%	0%	0%