A Simple Unpredictable Pseudo-Random Number Generator

Two closely-related pseudo-random sequence generators are presented: The 1 / Pgenerator, with input P a prime, outputs the quotient digits obtained on dividing 1 by P. The x² Ngenerator with inputs N, x₀ (where N = P Q is a product of distinct primes, each congruent to 3 mod 4, and x₀ is a quadratic residue N), outputs b₀ b₁ b₂ where bᵢ = parity (xᵢ) and x₈ + ₁ = xᵢ² N. From short seeds each generator efficiently produces long well-distributed sequences. Moreover, both generators have computationally hard problems at their core. The first generator’s sequences, however, are completely predictable (from any small segment of 2|P| + 1 consecutive digits one can infer the “seed, ” P, and continue the sequence backwards and forwards), whereas the second, under a certain intractability assumption, is unpredictable in a precise sense. The second generator has additional interesting properties: from knowledge of x₀ and N but notP or Q, one can generate the sequence forwards, but, under the above-mentioned intractability assumption, one can not generate the sequence backwards. From the additional knowledge of P and Q, one can generate the sequence backwards; one can even “jump” about from any point in the sequence to any other. Because of these properties, the x² Ngenerator promises many interesting applications, e. g. , to public-key cryptography. To use these generators in practice, an analysis is needed of various properties of these sequences such as their periods. This analysis is begun here.