Periodic orbits of the ensemble of Sinai-Arnold cat maps and pseudorandom number generation

We propose methods for constructing high-quality pseudorandom number generators (RNGs) based on an ensemble of hyperbolic automorphisms of the unit two-dimensional torus (Sinai-Arnold map or cat map) while keeping a part of the information hidden. The single cat map provides the random properties expected from a good RNG and is hence an appropriate building block for an RNG, although unnecessary correlations are always present in practice. We show that introducing hidden variables and introducing rotation in the RNG output, accompanied with the proper initialization, dramatically suppress these correlations. We analyze the mechanisms of the single-cat-map correlations analytically and show how to diminish them. We generalize the Percival-Vivaldi theory in the case of the ensemble of maps, find the period of the proposed RNG analytically, and also analyze its properties. We present efficient practical realizations for the RNGs and check our predictions numerically. We also test our RNGs using the known stringent batteries of statistical tests and find that the statistical properties of our best generators are not worse than those of other best modern generators.

Figure 1

Distribution of $P\left(K^{+}\right)$ and $P\left(K^{-}\right)$ for the frequency test. The test was performed for the RNG from Sec. 2 with the parameters $M=\left(\genfrac{}{}{0ex}{}{23}{35}\right)$, $g=2^m=2^{28}$, and $s=28$.

Figure 2

The deviation $\delta P_l$ of the probability of a walk length $l$ from the value for uncorrelated random numbers versus walk length $l$. The mean and the variance for $\delta P_l$ are represented for 100 chi-square random walk simulations. See the text for the details.

Figure 3

(Color online) Upper panel: the regions on the torus for the first initial point of the RNG described in Sec. 2 with $M=\left(\genfrac{}{}{0ex}{}{23}{35}\right)$. These regions correspond to the sequences 000, 001, 010, 011, 100, 101,110, and 111 of the first bits generated by the RNG. Each region is drawn with its own color. Lower panel: the regions on the torus for the third point of the RNG described in Sec. 2 with $M=\left(\genfrac{}{}{0ex}{}{11}{12}\right)$. These regions correspond to the sequences of length 5 of the first bits generated by the RNG. Each region is drawn with its own color.