** Next:** Randomness Used Inside the
** Up:** Pseudo Random Number Generators
** Previous:** arc4random(3)

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^{14} < *p* <
2^{15} and *g* a randomly chosen generator for . Being
a generator, *g* has the property that any value 0 < *x* < *p* can be
generated as , for some value *y*.

We then pick random *a*, *b* and *m* with 2^{14} < *m* < 2^{15} so that

becomes a linear congruential generator (LCG).
We then determine the actual ID as

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.

*& D. Keromytis*

*4/26/1999*