Random Walk in a N-Cube Without Hamiltonian Cycle to Chaotic Pseudorandom Number Generation: Theoretical and Practical Considerations

DOI10.1142/S0218127417500146MaRDI QIDQ2973273zbMATH OpenOpenAlexFDO

Authors S. Contassot-Vivier, Jean-François Couchot, Christophe Guyeux, Pierre-Cyrille Héam

Publication date 3 April 2017

Published in International Journal of Bifurcation and Chaos in Applied Sciences and Engineering (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1702.02533

zbMATH Keywords

chaotic iterationspseudorandom numbers generatorrandom walk

Mathematics Subject Classification ID

Pseudo-random numbers; Monte Carlo methods (11K45) Strange attractors, chaotic dynamics of systems with hyperbolic behavior (37D45) Sums of independent random variables; random walks (60G50)

Abstract: Designing a pseudorandom number generator (PRNG) is a difficult and complex task. Many recent works have considered chaotic functions as the basis of built PRNGs: the quality of the output would indeed be an obvious consequence of some chaos properties. However, there is no direct reasoning that goes from chaotic functions to uniform distribution of the output. Moreover, embedding such kind of functions into a PRNG does not necessarily allow to get a chaotic output, which could be required for simulating some chaotic behaviors. In a previous work, some of the authors have proposed the idea of walking into a $mathsfN$-cube where a balanced Hamiltonian cycle has been removed as the basis of a chaotic PRNG. In this article, all the difficult issues observed in the previous work have been tackled. The chaotic behavior of the whole PRNG is proven. The construction of the balanced Hamiltonian cycle is theoretically and practically solved. An upper bound of the expected length of the walk to obtain a uniform distribution is calculated. Finally practical experiments show that the generators successfully pass the classical statistical tests.

Recommendations

• Robust chaos of cubic polynomial discrete maps with application to pseudorandom number generators
• Chaos-based random number generators. Part II: practical realization
• A new nonrecursive pseudorandom number generator based on chaos mappings
• Cycles in random k-ary maps and the poor performance of random number generation
• p-adic Chaos and Random Number Generation
• Chaos-based random number generators-part I: analysis [cryptography]
• Quantifiers for randomness of chaotic pseudo-random number generators
• Pseudorandom number generator by p-adic chaos and Ramanujan expander graphs
• Generation of pseudo-random numbers from given probabilistic distribution with the use of chaotic maps
• Pseudorandom number generators based on chaotic dynamical systems

Cites work

• Balanced Gray codes
• Chaos-based random number generators-part I: analysis [cryptography]
• Chaos-based random number generators. Part II: practical realization
• Counting sequences
• scientific article; zbMATH DE number 44378 (Why is no real title available?)
• scientific article; zbMATH DE number 2239558 (Why is no real title available?)
• Mersenne twister
• On Devaney's Definition of Chaos
• On locally balanced Gray codes
• On the link between strongly connected iteration graphs and chaotic Boolean discrete-time dynamical systems
• Probability and Computing
• TestU01

Cited in

(3)

• Gray codes generation algorithm and theoretical evaluation of random walks in \(N\)-cubes
• Survey on hardware implementation of random number generators on FPGA: theory and experimental analyses
• Dynamics on binary relations over topological spaces

Describes a project that uses

Uses Software

• MersenneTwister
• Diehard
• TestU01

This page was built for publication: Random Walk in a N-Cube Without Hamiltonian Cycle to Chaotic Pseudorandom Number Generation: Theoretical and Practical Considerations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2973273)