Performance analysis of pseudo-random number generations of two-dimensional linear uniform cellular automata that considers initial state densities

Öz

İki boyutlu doğrusal tek tip hücresel özdevinirlerin başlangıç durum yoğunluklarını dikkate alan sözde rastgele sayı üretimlerinin başarım analizi

Öz

Bu çalışmada, iki boyutlu doğrusal tek tip hücresel özdevinirlerin başlangıç durum yoğunluklarının sözde-rastgele sayı üretimlerine olan etkisi deneysel olarak incelenmiştir. Çalışma, hücresel özdevinirlerin kaliteli sözde-rastgele sayı üretimlerinde başlangıç durum yoğunluklarının dikkate alınması açısından özgündür. Deneylerde dikkate alınan 512 adet iki boyutlu doğrusal hücresel özdevinir arasından (her birinin değerleri 0,05 ile 0,95 arasında değişen 19 adet farklı başlangıç durum yoğunlukları (ρ) için - toplam 512*19 = 9728 adet aday özdevinirin) 7 adedinin, uygulanan karşılaştırmalı istatistiksel testlerden yüksek başarıyla geçtikleri ve yetkin sözde-rastgele sayı üreteçleri oldukları, uygulanan National Institute of Standards and Technology (NIST) istatistiksel test süiti testleriyle doğrulanmıştır. Karşılaştırmalı çalışma neticesinde, bulunan hücresel özdevinir üreteçlerinin yetkin oldukları ve bunlardan en başarılı 2 adedinin, NIST test süitinde yer alan tümün üreteçlerden kümülatif ve kombine skor metrikleri dikkate alındığında daha iyi performans gösterdikleri gözlemlenmiştir. Özdevinirlerin başlangıç durum yoğunluk oranlarının sözde rastgele sayı üretimini etkilediği ve sözkonusu etkinin özdevinir tabanlı sözde rastgele sayı üretimi araştırmalarında dikkate alınması gereken bir unsur olduğu gösterilmiştir.

Anahtar Kelimeler

• Modelleme ve benzetim
• Sözde-rastgele sayı üretimi
• İki boyutlu doğrusal tek tip hücresel özdevinirler
• Başlangıç konfigürasyonu durum yoğunlukları
• NIST istatistiksel test süiti

Teşekkür

Atılım Üniversitesi, Metal Şekillendirme Mükemmeliyet Merkezi’ne; TÜBİTAK ULAKBİM Yüksek Başarımlı ve Grid Hesaplama Merkezi başuzmanı ve araştırmacısı Dr. Hakan Bayındır’a ve Atılım Üniversitesi bölüm asistanlarımız Ozan Can Acar, Buğra Yener Şahinoğlu ve İbrahim Tarakçı’ya faydalı soru, yorum ve desteklerinden dolayı teşekkür ederim.

Kaynakça

1. 1. Stipčević M., Koç Ç.K., (2014), “True random number generators”, In: Koç Ç.K., editor. Open Problems in Mathematics and Computational Science. Berlin, Germany: Springer, 275-315, 2014.
2. 2. Knuth D.E., The Art of Computer Programming, Addison-Wesley, Reading, Mass., ABD, 1981.
3. 3. Wolfram S., Random sequence generation by cellular automata, Adv. Appl. Math., 7, 123-169, 1986.
4. 4. Park S.K., Miller K.W., Random number generators: good ones are hard to find, Communications of ACM, 31, 1192-1201, 1988.
5. 5. Bakiri M., Guyeux C., Couchot J.F., Oudjida, A.K., Survey on hardware implementation of random number generators on FPGA: Theory and experimental analyses, Comput. Sci. Rev., 27, 135-153, 2018.
6. 6. Bhattacharjee K., Maity K., Das, S., Search for good pseudo-random Number Generators: Survey and Empirical Studies, arXiv:1811.04035 [cs.CR], 2018.
7. 7. Sipper M., Evolution of Parallel Cellular Machines: The Cellular Programming Approach, Lecture Notes in Computer Science - 1194, Springer-Verlag, Berlin, Heidelberg, Germany, 1997.
8. 8. Faraoun K.M., A genetic strategy to design cellular automata based block ciphers, Expert Syst. Appl., 41 (17), 7958-7967, 2014.

9. 9. Hanin C., Omary F., Elbernoussi S., Boulahiat B., Design of new pseudo-random number generator based on non-uniform cellular automata, International Journal of Security and its Applications, 10 (11), 109-118, 2016.
10. 10. Shin S.H., Kim D.S., Yoo K.Y., A 2-Dimensional Cellular Automata Pseudorandom Number Generator with Non-linear Neighborhood Relationship, Networked Digital Technologies, Springer-Verlag, 293, 355-368, 2012.
11. 11. Temiz F., Siap I., Akın H., On Pseudo Random Bit Generators via Two-Dimensional Hybrid Cellular Automata, Acta Phys. Pol. A, 125 (2), 534-537, 2014.
12. 12. Hosseini S.M., Karimi H., Jahan M.V., Generating pseudo-random numbers by combining two systems with complex behaviors, Journal of Information Security and Applications, 19 (2), 149-162, 2014.
13. 13. Szaban, M., (2019), Pseudorandom number generator based on totalistic cellular automaton, 15th International Conference on Parallel Computing Technologies (PaCT), Springer Series, Lecture Notes in Computer Science (LNCS) 11657, 360-370, 2019.
14. 14. Nayyeri A., Dastghaibyfard G., An Information Theoretic Analysis of Random Number Generator based on Cellular Automaton, International Journal of Advanced Computer Science and Applications, 9 (1), 321-329, 2018.
15. 15. Bhattacharjee K., Paul D., Das S., Pseudo-random number generation using a 3-state cellular automaton, Int. J. Mod. Phys. C, 28 (6): 1750078, 2017.
16. 16. Bhattacharjee K., Das, S., Random number generation using decimal cellular automata, Commun. Nonlinear Sci. Numer. Simul., 78, 104878, 2019.
17. 17. Guan S.U., Tan S.K., Pseudorandom number generation with self-programmable cellular automata, IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 23 (7), 1095-1101, 2004.
18. 18. Roy S., Gupta R.K., Rawat U., Dey N., Crespo R.G., PCHET: An efficient programmable cellular automata based hybrid encryption technique for multi-chat client-server applications, Journal of Information Security and Applications, 55, 102624, 2020.
19. 19. Petrica L., FPGA optimized cellular automaton random number generator, J. Parallel Distrib. Comput., 111, 251-259, 2018.
20. 20. Baetens J.M., Gravner J., Stability of Cellular Automata Trajectories Revisited: Branching Walks and Lyapunov Profiles, J. Nonlinear Sci., 26, 1329–1367, 2016.
21. 21. Rukhin, A., Soto, J., Nechvatal, J., Smid, M., Barker, E., Leigh, S., Levenson, M., Vangel, M., Banks, D., Heckert, A., Dray, J., Vo, S., “A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications”, National Institute of Standards and Technology (NIST) Special Publication 800-22 (Revision 1a, L. E. Bassham III), 2010.
22. 22. Packard N.H., Wolfram S., Two-Dimensional Cellular Automata, J. Stat. Phys., 38 (5-6), 901-946, 1985.
23. 23. Martinez G.J., Seck-Tuoh-Mora J.C., Zenil H., “Wolfram’s Classification and Computation in Cellular Automata Classes III and IV”, In: Zenil H. (eds) Irreducibility and Computational Equivalence. Emergence, Complexity and Computation, vol 2. Springer, Berlin, Heidelberg, 2013.
24. 24. Zenil H., Compression-based Investigation of the Dynamical Properties of Cellular Automata and Other Systems, Complex Syst., 19 (1), 1-28, 2010.
25. 25. Culik K, Yu S., Undecidability of CA classification schemes, Complex Syst., 2 (2), 177-190, 1988.
26. 26. Tomassini M., Sipper M., Perrenoud M., On the Generation of High-Quality Random Numbers by Two-Dimensional Cellular Automata, IEEE Trans. Comput., 49 (10), 1146-1151, 2000.