A New Statistical Randomness Test: Saturation Point Test

Abstract

In this work, we propose a new statistical randomness test, the Saturation Point Test, which can be applied to integer sequences as well as binary sequences and is designed to increase the number of tests for short sequences. The subject of Saturation Point Test is the index of integer, denoted by SP, where all possible integers occur in the given sequence. We evaluate the probability Pr(SP=t) using Stirling numbers of the second kind and give a procedure to produce a p-value using this probability. Moreover, we state a pseudocode for the new test and evaluate the subinterval probabilities to apply chi^2 goodness of fit test.

Keywords

• Saturation Point
• Statistical Randomness Test
• Stirling Numbers of the Second Kind

References

1. A. J. Menezes, P. C. van Oorschot, S. A. Vanstone, Handbook of Applied Cryptography, CRC Press, 2001.
2. A. Rukhin, J. Soto, J. Nechvatal, M. Smid, E. Barker, S. Leigh, M. Levenson, M. Vangel, D. Banks, A. Heckert, J. Dray, S. Vo, A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications, NIST Special Pub- lication 800-22, 2001
3. D. E. Knuth, Seminumerical Algorithms, The Art of Computer Programming, vol 2, Addison-Wesley, 1981.
4. R. L. Graham, D. E. Knuth, O. Patashnik, Concrete Mathematics, Addison-Wesley, 1988.
5. G. Blom, L. Holst, D. Sandell, Problems and Snapshots from the World of Probability, Springer-Verlag, 1994.
6. P. L’Ecuyer, R. Simard, TestU01: A C library for empirical testing of random number generators, ACM Trans. Math. Softw., vol. 33, no. 4, p.22, 2007.
7. W. Caelli, E. Dawson, L. Nielsen, H. Gustafson, CRYPT–X Statistical Package Manual, Measuring the strength of Stream and Block Ciphers, Queensland University of Technology, 1992.
8. G. Marsaglia, The Marsaglia Random Number CDROM includ- ing the DIEHARD Battery of Tests of Randomness, preprint, 1996. http://stat.fsu.edu/pub/diehard

9. F. Sulak, A. Do˘ganaksoy, B. Ege, O. Koc¸ak, Evaluation of Randomness Test Results for Short Sequences, Claude Carlet and Alexander Pott Ed., in Proc. Sixth Conference on Sequences and Their Applications. SETA 2010, Paris, 2010, vol. LNCS 6338, pp.309-319. Appendix TABLE 2 P-Value Table for the Saturation Point Test T -value p-value 0,000002 0,000019 0,000089 0,000292 0,000774 0,001752 0,003522 0,006442 0,010921 0,017385 0,026255 0,037918 0,052704 0,070868 0,092580 0,117922 0,146887 0,179384 0,215250 0,254260 0,296138 0,340570 0,387218 0,435729 0,485746 0,469636 40 ∞