×

zbMATH — the first resource for mathematics

R-2 composition tests: a family of statistical randomness tests for a collection of binary sequences. (English) Zbl 1419.94050
Summary: In this article a family of statistical randomness tests for binary strings are introduced, based on Golomb’s pseudorandomness postulate R-2 on the number of runs. The basic idea is to construct recursive formulae with computationally tenable probability distribution functions. The technique is illustrated on testing strings of \( 2^7, 2^8, 2^{10} \) and \( 2^{12} \) bits. Furthermore, the expected value of the number of runs with a specific length is obtained. Finally the tests are applied to several collections of strings arising from different pseudorandom number generators.
MSC:
94A60 Cryptography
94A55 Shift register sequences and sequences over finite alphabets in information and communication theory
05A15 Exact enumeration problems, generating functions
05A17 Combinatorial aspects of partitions of integers
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Golomb, W.S.: Shift Register Sequences. Aegean Park Press, Laguna Hills (1982) · Zbl 1152.94383
[2] Knuth, D.E.: The Art of Computer Programming, 3rd edn., vol. 2, Addison-Wesley Longman Publishing Co., Inc., Seminumerical Algorithms, Boston (1997) · Zbl 0883.68015
[3] L’ecuyer, P.; Simard, R., Testu01: A C library for empirical testing of random number generators, ACM Trans. Math. Softw., 33, 22, (2007) · Zbl 1365.65008
[4] Mood, AM, The distribution theory of runs, Ann. Math. Stat., 11.4, 367-392, (1940) · Zbl 0024.05301
[5] Fu, JC; Koutras, MV, Distribution theory of runs: a Markov chain approach, J. Am. Stat. Assoc., 89.427, 1050-1058, (1994) · Zbl 0806.60011
[6] Marsaglia, G.: The Marsaglia Random Rumber CDROM Including the Diehard Battery of Tests of Tandomness, http://www.stat.fsu.edu/pub/diehard/ (1995)
[7] Bassham III, L.E., Rukhin, A.L., Soto, J., et al.: A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications. Tech. Rep Sp 800-22 Rev. 1a, NIST, Gaithersburg (2010)
[8] Doğanaksoy, A.; Sulak, F.; Uğuz, M.; Şeker, O.; Akcengiz, Z., New statistical randomness tests based on length of runs, Math. Probl. Eng., 2015, 14, (2015) · Zbl 1395.94280
[9] van Lint, J.H., Wilson, R.M.: A Course in Combinatorics. Cambridge University Press, New York (1993) · Zbl 0769.05001
[10] Chinn, P.; Heubach, S., Compositions of n with no occurence of k, Congressus Numerantium, 164, 33-51, (2003) · Zbl 1044.05007
[11] Heubach, S.; Mansour, T., Compositions of n with Parts in a Set, Congressus Numerantium, 168, 127-143, (2004) · Zbl 1067.05004
[12] Richmond, B.; Knopfmacher, A., Compositions with distinct parts, Aequationes Math., 49, 86-87, (1995) · Zbl 0824.11065
[13] Malandro, M.E.: Integer Compositions with Part Sizes not Exceeding k, Preprint available at: https://arxiv.org/pdf/1108.0337v2.pdf (2012)
[14] Munagi, AO; Sellers, JA, Some inplace identities for integer compositions, Quaest. Math., 38, 535-540, (2015) · Zbl 1397.11145
[15] Chinn, P.; Heubach, S., (1,K)-compositions, Congressus Numerantium, 164, 183-194, (2003) · Zbl 1045.05001
[16] Jaklic, G.; Vitrih, V.; Zagar, E., Closed form formula for the number of restricted compositions, Bull. Aus. Math. Soc., 81, 289-297, (2010) · Zbl 1226.05039
[17] Sulak, F., Doğanaksoy, A., Ege, B., Koçak, O.: Evaluation of Randomness Test Results for Short Sequences, Sequences and Their Applications, vol. 6338, pp 310-319. SETA 2010, Lecture Notes in Computer Science, Berlin (2010) · Zbl 1257.62128
[18] Daeman, J., Rijmen, V.: The Design of Rijndael: AES - the Advanced Encryption Standard. Springer, Berlin (2002) · Zbl 1065.94005
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.