Non-repeating Random Numbers

  In OpenBSD, we designed a non-repeating pseudo-random number generator that was very fast and did not require additional resources.

For 16-bit non-repeating numbers, we used a prime 2¹⁴ < p < 2¹⁵ and g a randomly chosen generator for $\mathbbm{Z}_p$. Being a generator, g has the property that any value 0 < x < p can be generated as $x = g^{y} \pmod{p}$, for some value y.

We then pick random a, b and m with 2¹⁴ < m < 2¹⁵ so that

$$f(n) \equiv a \cdot f(n-1) + b \pmod{m}$$

becomes a linear congruential generator (LCG).

We then determine the actual ID as

$$ID(n) = w \oplus (g^{f(n)}\!\!\mod{p}),$$

where w is a random seed. After the linear congruential generator has been exhausted, the most significant bit in ID(n) is toggled and all parameters g, a, b, m, and w from above are chosen anew. Because the linear congruential generator does not repeat itself and a new number space is chosen after reinitialization, the generated IDs do not repeat themselves. The PRNG is typically seeded with material from the kernel randomness pool.