Xorshift random number generators from primitive polynomials

• Autorzy: Kumar Bishoi S. , Narayan Maharana S.

Identyfikatory

DOI

10.20904/291-2001

• Języki publikacji: EN

Abstrakty

EN

A class of Xorshift Random Number Generators (RNGs) are introduced by Marsaglia. We have proposed an algorithm which constructs a primitive Xorshift RNG from a given prim- itive polynomial. We also have shown a weakness present in those RNGs and suggested its solution. A separate algorithm also proposed which returns a full periodic Xorshift generator with desired number of Xorshift operations.

Słowa kluczowe

EN

random number generators; Xorshift generator; primitive polynomials; linear feed-back shift registers; multiple-recursive matrix method

PL

generatory liczb losowych; generator Xorshift

• Wydawca: Instytut Informatyki Teoretycznej i Stosowanej Polskiej Akademii Nauk
• Czasopismo: Theoretical and Applied Informatics
• Rocznik: 2017
• Tom: Vol. 29, No. 1-2
• Strony: 1--13
• Opis fizyczny: Bibliogr. 19 poz.

Twórcy

autor

Kumar Bishoi S.

• Center for Artificial Intelligence and Robotics, Defence Research and Development Organisation, CV Raman Nagar, Bengaluru 560093, India
• Faculty of Informatics, Masaryk Univerzity, Czechia

autor

Narayan Maharana S.

• Indian Institute of Technology, Ropar, Punjab 140001, India

Bibliografia

• [1] S. W. Golomb. Shift Register Sequences. Cambridge University Press, 1967.
• [2] R. Lidl and H. Niederreiter. Finite fields. Cambridge University Press, 1996. DOI: 10.1017/cbo9780511525926.
• [3] S. R. Ghorpade, S. U. Hasan, and M. Kumari. Primitive polynomials, singer cycles and word-oriented linear feedback shift registers. Designs, Codes and Cryptography, 58(2):123-134, 2011. DOI: 10.1007/s10623-010-9387-7.
• [4] H. Niederreiter. The Multiple-Recursive Matrix Method for Pseudorandom Number Generation. Finite Fields and Their Applications, 1(1):3-30, 1995. DOI: 10.1006/ta.1995.1002.
• [5] H. Niederreiter. Pseudorandom vector generation by the multiple-recursive matrix method.Mathematics of Computation, 64(209):279-294, 1995. DOI: 10.1090/s0025-5718-1995-1265018-4.
• [6] H. Niederreiter. Improved Bounds in the Multiple-Recursive Matrix Method for Pseudorandom Number and Vector Generation. Finite Fields and Their Applications, 2(3):225-240,1996. DOI: 10.1006/ta.1996.0015.
• [7] G. Zeng, W. Han, and K. He. Word-oriented feedback shift register: σ-LFSR. Cryptology ePrint Archive: Report 2007/114, 2007.
• [8] R. P. Brent. On the periods of generalized Fibonacci recurrences. Mathematics of Computation, 63(207):389-389, 1994. DOI: 10.1090/s0025-5718-1994-1216256-7.
• [9] F. Panneton and P. L'ecuyer. On the xorshift random number generators. ACM Transactions on Modeling and Computer Simulation, 15(4):346-361, 2005. DOI: 10.1145/1113316.1113319.
• [10] A. J Menezes, P. C. Van Oorschot, and S. A. Vanstone. Handbook of applied cryptography. CRC press, 1996.
• [11] D. R. Stinson. Cryptography: theory and practice. CRC press, 2006.
• [12] S. K. Bishoi, H. K. Haran, and S. U. Hasan. A note on the multiple-recursive matrix method for generating pseudorandom vectors. Discrete Applied Mathematics, 222:67-75, 2017. DOI: 10.1016/j.dam.2017.01.033.
• [13] S. K. Bishoi and V. Matyas. Investigating results and performance of search and construction algorithms for word-based LFSRs, -LFSRs. Discrete Applied Mathematics, 2018. Accepted for publication.
• [14] G. Marsaglia. Xorshift RNGs. Journal of Statistical Software, 8(14), 2003. DOI:10.18637/jss.v008.i14.
• [15] D. Knuth et al. The Art of Computer Programming, Volume 2: Semi numerical Algorithms. Addison-Wesley Longman, Inc, 1998.
• [16] V. Chepyzhov and B. Smeets. On A Fast Correlation Attack on Certain Stream Ciphers. In Advances in Cryptology | EUROCRYPT '91, pages 176-185. Springer Berlin Heidelberg. DOI: 10.1007/3-540-46416-6 16.
• [17] V. V. Chepyzhov, T. J., and B. Smeets. A Simple Algorithm for Fast Correlation Attacks on Stream Ciphers. In Fast Software Encryption, pages 181-195. Springer Berlin Heidelberg, 2001. DOI: 10.1007/3-540-44706-7 13.
• [18] P. R. Mishra, I. Gupta, and N. Gaba. Distribution of Primitive Polynomials Over GF(2) with Respect to Their Weights. In Mathematics and Computing, pages 441-449. Springer India, 2015. DOI: 10.1007/978-81-322-2452-5 30.
• [19] A. Compagner. The hierarchy of correlations in random binary sequences. Journal of Statistical Physics, 63(5-6):883-896, 1991. DOI: 10.1007/bf01029989.

Uwagi

PL

Opracowanie w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018).