Previous: Lucas Numbers Algorithm, Up: Other Algorithms [Index]

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.

Previous: Lucas Numbers Algorithm, Up: Other Algorithms [Index]