(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