(gmp.info.gz) Random Number Algorithms
Info Catalog
(gmp.info.gz) Lucas Numbers Algorithm
(gmp.info.gz) Other Algorithms
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 (
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 ( References). With a modulus M and
parameters A and C, a 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.
Info Catalog
(gmp.info.gz) Lucas Numbers Algorithm
(gmp.info.gz) Other Algorithms
automatically generated byinfo2html