c_cpp/etc/calc/help/random

   1 NAME
   2     random - Blum-Blum-Shub pseudo-random number generator
   3
   4 SYNOPSIS
   5     random([[min, ] beyond])
   6
   7 TYPES
   8     min         integer
   9     beyond      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:
  16
  17         [min,beyond)    ((min <= return < beyond))
  18
  19     By default, min is 0 and beyond is 2^64.
  20
  21     While the Blum-Blum-Shub generator is not painfully slow, it is not
  22     a fast generator.  For a faster, but lesser quality generator
  23     (non-cryptographically strong) see the additive 55 generator
  24     (see the rand help page).
  25
  26     Other arg forms:
  27
  28         random()        Same as random(0, 2^64)
  29         random(beyond)  Same as random(0, beyond)
  30
  31     The random generator generates the highest order bit first.  Thus:
  32
  33         random(256)
  34
  35     will produce the save value as:
  36
  37         (random(8) << 5) + random(32)
  38
  39     when seeded with the same seed.
  40
  41     The basic idea behind the Blum-Blum-Shub generator is to use
  42     the low bit bits of quadratic residues modulo a product of
  43     two 3 mod 4 primes.  The lowest int(log2(log2(p*q))) bits are used
  44     where log2() is log base 2 and p,q are two primes 3 mod 4.
  45
  46     The Blum-Blum-Shub generator is described in the papers:
  47
  48         Blum, Blum, and Shub, "Comparison of Two Pseudorandom Number
  49         Generators", in Chaum, D. et. al., "Advances in Cryptology:
  50         Proceedings Crypto 82", pp. 61-79, Plenum Press, 1983.
  51
  52         Blum, Blum, and Shub, "A Simple Unpredictable Pseudo-Random
  53         Number Generator", SIAM Journal of Computing, v. 15, n. 2,
  54         1986, pp. 364-383.
  55
  56         U. V. Vazirani and V. V. Vazirani, "Trapdoor Pseudo-Random
  57         Number Generators with Applications to Protocol Design",
  58         Proceedings of the 24th  IEEE Symposium on the Foundations
  59         of Computer Science, 1983, pp. 23-30.
  60
  61         U. V. Vazirani and V. V. Vazirani, "Efficient and Secure
  62         Pseudo-Random Number Generation", Proceedings of the 24th
  63         IEEE Symposium on the Foundations of Computer Science,
  64         1984, pp. 458-463.
  65
  66         U. V. Vazirani and V. V. Vazirani, "Efficient and Secure
  67         Pseudo-Random Number Generation", Advances in Cryptology -
  68         Proceedings of CRYPTO '84, Berlin: Springer-Verlag, 1985,
  69         pp. 193-202.
  70
  71         Sciences 28, pp. 270-299.
  72
  73         Bruce Schneier, "Applied Cryptography", John Wiley & Sons,
  74         1st edition (1994), pp 365-366.
  75
  76     This generator is considered 'strong' in that it passes all
  77     polynomial-time statistical tests.  The sequences produced are
  78     random in an absolutely precise way.  There is absolutely no better
  79     way to predict the sequence than by tossing a coin (as with TRULY
  80     random numbers) EVEN IF YOU KNOW THE MODULUS!  Furthermore, having
  81     a large chunk of output from the sequence does not help.  The BITS
  82     THAT FOLLOW OR PRECEDE A SEQUENCE ARE UNPREDICTABLE!
  83
  84     Of course the Blum modulus should have a long period.  The default
  85     Blum modulus as well as the compiled in Blum moduli have very long
  86     periods.  When using your own Blum modulus, a little care is needed
  87     to avoid generators with very short periods.  See the srandom()
  88     help page for information for more details.
  89
  90     To compromise the generator, an adversary must either factor the
  91     modulus or perform an exhaustive search just to determine the next
  92     (or previous) bit.  If we make the modulus hard to factor (such as
  93     the product of two large well chosen primes) breaking the sequence
  94     could be intractable for todays computers and methods.
  95
  96     The Blum generator is the best generator in this package.  It
  97     produces a cryptographically strong pseudo-random bit sequence.
  98     Internally, a fixed number of bits are generated after each
  99     generator iteration.  Any unused bits are saved for the next call
 100     to the generator.  The Blum generator is not too slow, though
 101     seeding the generator via srandom(seed,plen,qlen) can be slow.
 102     Shortcuts and pre-defined generators have been provided for this
 103     reason.  Use of Blum should be more than acceptable for many
 104     applications.
 105
 106     The goals of this package are:
 107
 108         all magic numbers are explained
 109
 110             I distrust systems with constants (magic numbers) and tables
 111             that have no justification (e.g., DES).  I believe that I have
 112             done my best to justify all of the magic numbers used.
 113
 114          full documentation
 115
 116             You have this source file, plus background publications,
 117             what more could you ask?
 118
 119         large selection of seeds
 120
 121             Seeds are not limited to a small number of bits.  A seed
 122             may be of any size.
 123
 124         the strength of the generators may be tuned to meet the need
 125
 126             By using the appropriate seed and other arguments, one may
 127             increase the strength of the generator to suit the need of
 128             the application.  One does not have just a few levels.
 129
 130     For a detailed discussion on seeds, see the srandom help page.
 131
 132     It should be noted that the factors of the default Blum modulus
 133     is given in the source.  While this does not reduce the quality
 134     of the generator, knowing the factors of the Blum modulus would
 135     help someone determine the next or previous bit when they did
 136     not know the seed.  If this bothers you, feel free to use one
 137     of the other compiled in Blum moduli or provide your own. See
 138     the srandom help page for details.
 139
 140
 141 EXAMPLE
 142     ; print srandom(0), random(), random(), random()
 143     RANDOM state 9203168135432720454 13391974640168007611 13954330032848846793
 144
 145     ; print random(123), random(123), random(123), random(123), random(123)
 146     22 83 66 88 67
 147
 148     ; print random(2,12), random(2^50,3^50), random(0,2), random(-400000,120000)
 149     10 483381144668580304003305 0 -70235
 150
 151 LIMITS
 152     min < beyond
 153
 154 LINK LIBRARY
 155     void zrandom(long cnt, ZVALUE *res)
 156     void zrandomrange(ZVALUE low, ZVALUE beyond, ZVALUE *res)
 157     long irandom(long beyond)
 158
 159 SEE ALSO
 160     seed, srand, randbit, isrand, rand, srandom, israndom
 161
 162 ## Copyright (C) 1999-2007  Landon Curt Noll
 163 ##
 164 ## Calc is open software; you can redistribute it and/or modify it under
 165 ## the terms of the version 2.1 of the GNU Lesser General Public License
 166 ## as published by the Free Software Foundation.
 167 ##
 168 ## Calc is distributed in the hope that it will be useful, but WITHOUT
 169 ## ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
 170 ## or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General
 171 ## Public License for more details.
 172 ##
 173 ## A copy of version 2.1 of the GNU Lesser General Public License is
 174 ## distributed with calc under the filename COPYING-LGPL.  You should have
 175 ## received a copy with calc; if not, write to Free Software Foundation, Inc.
 176 ## 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 177 ##
 178 ## @(#) $Revision: 30.3 $
 179 ## @(#) $Id: random,v 30.3 2007/09/21 02:16:29 chongo Exp $
 180 ## @(#) $Source: /usr/local/src/cmd/calc/help/RCS/random,v $
 181 ##
 182 ## Under source code control:   1997/02/17 01:18:22
 183 ## File existed as early as:    1997
 184 ##
 185 ## chongo <was here> /\oo/\     http://www.isthe.com/chongo/
 186 ## Share and enjoy!  :-)        http://www.isthe.com/chongo/tech/comp/calc/