15.7.6 Random Numbers

For the urandomb functions, random numbers are generated simply by concatenating bits produced by the generator. As long as the generator has good randomness properties this will produce well-distributed N bit numbers.

For the urandomm functions, random numbers in a range 0<=R<N are generated by taking values R of ceil(log2(N)) bits each until one satisfies R<N. This will normally require only one or two attempts, but the attempts are limited in case the generator is somehow degenerate and produces only 1 bits or similar.

The Mersenne Twister generator is by Matsumoto and Nishimura (see References). It has a non-repeating period of 2^19937-1, which is a Mersenne prime, hence the name of the generator. The state is 624 words of 32-bits each, which is iterated with one XOR and shift for each 32-bit word generated, making the algorithm very fast. Randomness properties are also very good and this is the default algorithm used by GMP.

Linear congruential generators are described in many text books, for instance Knuth volume 2 (see References). With a modulus M and parameters A and C, an integer state S is iterated by the formula S <- A*S+C mod M. At each step the new state is a linear function of the previous, mod M, hence the name of the generator.

In GMP only moduli of the form 2^N are supported, and the current implementation is not as well optimized as it could be. Overheads are significant when N is small, and when N is large clearly the multiply at each step will become slow. This is not a big concern, since the Mersenne Twister generator is better in every respect and is therefore recommended for all normal applications.

For both generators the current state can be deduced by observing enough output and applying some linear algebra (over GF(2) in the case of the Mersenne Twister). This generally means raw output is unsuitable for cryptographic applications without further hashing or the like.