Hyperbolic automorphisms of tori and pseudo-random sequences

A method for generating pseudo-random sequences of d-dimensional vectors is considered; it is based on the ergodic theory of periodic orbits in the sense of [2] for unstable dynamical systems such as the hyperbolic automorphisms of the d-dimensional Torus. Since these systems enjoy strong chaotic properties, their orbits are both dense and chaotic in some sense, however the ergodic property holds only for orbits having initial points with irrational coordinates, the remaining ones being periodic. Unfortunately, those orbits are the only ones that a computer is able to generate. Since a pseudo-random sequence in [0,1] d is a long periodic orbit which has chaotic behaviour similar in some sense to the one of aperiodic orbits, in this note, we shall prove lower and upper bounds for the length of the period of orbits of the hyperbolic automorphisms of the d-dimensional Torus, expressed in terms of the (rational) starting point. The algorithms proposed are free of computational error, since they work in integer arithmetic. Surprisingly the elimination of the round off errors turns out in an increase of the length of the period. Statistical testing and the problem of estimating the discrepancy of the obtained sequences are also treated. © 1992 Instituto di Elaborazione della Informazione del CNR