help/random

   1 NAME
   2     random - Blum-Blum-Shub pseudo-random number generator
   3
   4 SYNOPSIS
   5     random([[min, ] max])
   6
   7 TYPES
   8     min         integer
   9     max         integer
  10
  11     return      integer
  12
  13 DESCRIPTION
  14     Generate a pseudo-random number using a Blum-Blum-Shub generator.
  15     We return a pseudo-random number over the half closed interval [min,max).
  16     By default, min is 0 and max is 2^64.
  17
  18     While the Blum-Blum-Shub generator is not painfully slow, it is not
  19     a fast generator.  For a faster, but lesser quality generator
  20     (non-cryptographically strong) see the additive 55 generator
  21     (see the rand help page).
  22
  23     Other arg forms:
  24
  25         random()        Same as rand(0, 2^64)
  26         random(max)     Same as rand(0, max)
  27
  28     The random generator generates the highest order bit first.  Thus:
  29
  30         random(256)
  31
  32     will produce the save value as:
  33
  34         (random(8) << 5) + random(32)
  35
  36     when seeded with the same seed.
  37
  38     The basic idea behind the Blum-Blum-Shub generator is to use
  39     the low bit bits of quadratic residues modulo a product of
  40     two 3 mod 4 primes.  The lowest int(log2(log2(p*q))) bits are used
  41     where log2() is log base 2 and p,q are two primes 3 mod 4.
  42
  43     The Blum-Blum-Shub generator is described in the papers:
  44
  45         Blum, Blum, and Shub, "Comparison of Two Pseudorandom Number
  46         Generators", in Chaum, D. et. al., "Advances in Cryptology:
  47         Proceedings Crypto 82", pp. 61-79, Plenum Press, 1983.
  48
  49         Blum, Blum, and Shub, "A Simple Unpredictable Pseudo-Random
  50         Number Generator", SIAM Journal of Computing, v. 15, n. 2,
  51         1986, pp. 364-383.
  52
  53         U. V. Vazirani and V. V. Vazirani, "Trapdoor Pseudo-Random
  54         Number Generators with Applications to Protocol Design",
  55         Proceedings of the 24th  IEEE Symposium on the Foundations
  56         of Computer Science, 1983, pp. 23-30.
  57
  58         U. V. Vazirani and V. V. Vazirani, "Efficient and Secure
  59         Pseudo-Random Number Generation", Proceedings of the 24th
  60         IEEE Symposium on the Foundations of Computer Science,
  61         1984, pp. 458-463.
  62
  63         U. V. Vazirani and V. V. Vazirani, "Efficient and Secure
  64         Pseudo-Random Number Generation", Advances in Cryptology -
  65         Proceedings of CRYPTO '84, Berlin: Springer-Verlag, 1985,
  66         pp. 193-202.
  67
  68         Sciences 28, pp. 270-299.
  69
  70         Bruce Schneier, "Applied Cryptography", John Wiley & Sons,
  71         1st edition (1994), pp 365-366.
  72
  73     This generator is considered 'strong' in that it passes all
  74     polynomial-time statistical tests.  The sequences produced are
  75     random in an absolutely precise way.  There is absolutely no better
  76     way to predict the sequence than by tossing a coin (as with TRULY
  77     random numbers) EVEN IF YOU KNOW THE MODULUS!  Furthermore, having
  78     a large chunk of output from the sequence does not help.  The BITS
  79     THAT FOLLOW OR PRECEDE A SEQUENCE ARE UNPREDICTABLE!
  80
  81     Of course the Blum modulus should have a long period.  The default
  82     Blum modulus as well as the compiled in Blum moduli have very long
  83     periods.  When using your own Blum modulus, a little care is needed
  84     to avoid generators with very short periods.  See the srandom()
  85     help page for information for more details.
  86
  87     To compromise the generator, an adversary must either factor the
  88     modulus or perform an exhaustive search just to determine the next
  89     (or previous) bit.  If we make the modulus hard to factor (such as
  90     the product of two large well chosen primes) breaking the sequence
  91     could be intractable for todays computers and methods.
  92
  93     The Blum generator is the best generator in this package.  It
  94     produces a cryptographically strong pseudo-random bit sequence.
  95     Internally, a fixed number of bits are generated after each
  96     generator iteration.  Any unused bits are saved for the next call
  97     to the generator.  The Blum generator is not too slow, though
  98     seeding the generator via srandom(seed,plen,qlen) can be slow.
  99     Shortcuts and pre-defined generators have been provided for this
 100     reason.  Use of Blum should be more than acceptable for many
 101     applications.
 102
 103     The goals of this package are:
 104
 105         all magic numbers are explained
 106
 107             I distrust systems with constants (magic numbers) and tables
 108             that have no justification (e.g., DES).  I believe that I have
 109             done my best to justify all of the magic numbers used.
 110
 111          full documentation
 112
 113             You have this source file, plus background publications,
 114             what more could you ask?
 115
 116         large selection of seeds
 117
 118             Seeds are not limited to a small number of bits.  A seed
 119             may be of any size.
 120
 121         the strength of the generators may be tuned to meet the need
 122
 123             By using the appropriate seed and other arguments, one may
 124             increase the strength of the generator to suit the need of
 125             the application.  One does not have just a few levels.
 126
 127     For a detailed discussion on seeds, see the srandom help page.
 128
 129     It should be noted that the factors of the default Blum modulus
 130     is given in the source.  While this does not reduce the quality
 131     of the generator, knowing the factors of the Blum modulus would
 132     help someone determine the next or previous bit when they did
 133     not know the seed.  If this bothers you, feel free to use one
 134     of the other compiled in Blum moduli or provide your own. See
 135     the srandom help page for details.
 136
 137
 138 EXAMPLE
 139     > print srandom(0), random(), random(), random()
 140     RANDOM state 9203168135432720454 13391974640168007611 13954330032848846793
 141
 142     > print random(123), random(123), random(123), random(123), random(123)
 143     22 83 66 88 67
 144
 145     > print random(2,12), random(2^50,3^50), random(0,2), random(-400000,120000)
 146     10 483381144668580304003305 0 -70235
 147
 148 LIMITS
 149     min < max
 150
 151 LINK LIBRARY
 152     void zrandom(long cnt, ZVALUE *res)
 153     void zrandomrange(ZVALUE low, ZVALUE high, ZVALUE *res)
 154     long irandom(long max)
 155
 156 SEE ALSO
 157     seed, srand, randbit, isrand, rand, srandom, israndom
 158