Generating Uniform Random Vectors

In this paper, we study the rate of convergence of the Markov chain X_n+1=AX_n+b_n mod p, where A is an integer matrix with nonzero integer eigenvalues and {b_n}_n is a sequence of independent and identically distributed integer vectors. If _i±1 for all eigenvalues _i of A, then n=O((log p)²) steps are sufficient and n=O(log p) steps are necessary to have X_n sampling from a nearly uniform distribution. Conversely, if A has the eigenvalue ₁=±1, and _i±1 for all i1, n=O(p²) steps are necessary and sufficient.