Title: Random Walk in a N-cube Without Hamiltonian Cycle to Chaotic Pseudorandom Number Generation: Theoretical and Practical Considerations,
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 $\mathsf{N}$-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.