Xorshift Random Number Generators From Primitive Polynomials

Susil Kumar Bishoi, Surya Narayan Maharana

Abstract


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.

Full Text:

PDF

References


S. W. Golomb, Shift Register Sequences, Cambridge University Press, 1967.

R. Lidl and H. Niederreiter, Finite fields, Cambridge University Press, 1996, DOI: 10.1017/cbo9780511525926

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

H. Niederreiter, The Multiple-Recursive Matrix Method for Pseudorandom Number Generation, Finite Fields and Their Applications, 1(1):3-30, 1995, DOI: 10.1006/ffta.1995.1002

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

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/ffta.1996.0015

G. Zeng, W. Han, and K. He, Word-oriented feedback shift register: σ-LFSR, Cryptology ePrint Archive: Report 2007/114, 2007.

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

F. Panneton and P. Lecuyer, On the xorshift random number generators, ACM Transactions on Modeling and Computer Simulation. 15(4):346-361, 2005, DOI: 10.1145/1113316.1113319

A. J Menezes, P. C. Van Oorschot, and S. A. Vanstone, Handbook of applied cryptography, CRC press, 1996.

D. R. Stinson, Cryptography: theory and practice, CRC press, 2006.

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

S. K. Bishoi and V. Matyas, Investigating results and performance of search and construction algorithms for word-based LFSRs, , Discrete Applied Mathematics, 2018, Accepted for publication.

G. Marsaglia, Xorshift RNGs, Journal of Statistical Software, 8(14), 2003, DOI: 10.18637/jss.v008.i14

D. Knuth et al, The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Addison-Wesley Longman, Inc, 1998.

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

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

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

A. Compagner, The hierarchy of correlations in random binary sequences, Journal of Statistical Physics, 63(5-6):883-896, 1991, DOI: 10.1007/bf01029989




DOI: http://dx.doi.org/10.20904/291-2001

Refbacks

  • There are currently no refbacks.


Copyright (c) 2018 Susil Kumar Bishoi, Surya Narayan Maharana

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

ISSN: 1896-5334 (print), 2300-889X (online)

Open Acces CrossRef Indexed in DOAJ